强大的双指针法-leetcode15. 三数之和

青出于蓝而胜于蓝，三数求和虽然和两数求和只差了一个字，但是思路却完全不同。

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。
15. 三数之和

双指针法用在涉及求和、比大小类的数组题目里时，大前提往往是：该数组必须有序。否则双指针根本无法帮助我们缩小定位的范围，压根没有意义。因此这道题的第一步是将数组排序：

先把数组从小到大排序

var threeSum = function (nums: number[]) {
    // 先对数组进行排序！
    nums = nums.sort((a, b) => a - b)
};

threeSum([-1, 0, 1, 2, -1, -4])

[ -4, -1, -1, 0, 1, 2 ]

然后对数组进行遍历，每次遍历到哪个数字，就固定哪个数字。（注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数，所以全部循环次数只有num.length-2）

var threeSum = function (nums: number[]) {

    // 先对数组进行排序！
    nums = nums.sort((a, b) => a - b)
    
    //注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数，所以全部循环次数只有`num.length-2`）
    for (let i = 0; i < nums.length - 2; i++) {
    
    }
};

然后把左指针指向该固定数字的后一位！，把右指针指向数组末尾，让左右指针从起点开始，向中间前进

从初始位置开始：小于0，如果当前的小于0，那么就让左指针往右移动，找大一点的！
反之：如果当前的大于0，那么就让右指针往左移动，找小一点的！

 /**
 * @param {number[]} nums
 * @return {number[][]}
 * 
示例 1：
    输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]
示例 2：
    输入：nums = []
    输出：[]
示例 3：
    输入：nums = [0]
    输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
var threeSum = function (nums: number[]) {
    let ret: number[][] = []
    // 先对数组进行从小到大排序！
    nums = nums.sort((a, b) => a - b); //[ -4, -1, -1, 0, 1, 2 ]
    //注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数，所以全部循环次数只有`num.length-2`）
    for (let i = 0; i < nums.length - 2; i++) {
        let l = i + 1;
        let r = nums.length - 1;
        while (l < r) {
            if (nums[i] + nums[l] + nums[r] < 0) {
                // 因为排序是从小到大的，如果当前的小于0，那么就让左指针往右移动，找大一点的！
                l += 1
            } else if (nums[i] + nums[l] + nums[r] > 0) {
                // 因为排序是从大到小的，如果当前的大于0，那么就让右指针往左移动，找小一点的！
                r -= 1
            } else {
                // 如果找到了，那么就存起来，并且同时向内移动一位继续寻找！
                ret.push([nums[i], nums[l], nums[r]])
                l += 1;
                r -= 1;
            }
        }
    }
    console.log('====================================');
    console.log(ret);
    console.log('====================================');
};
threeSum([-1, 0, 1, 2, -1, -4])

输出结果：

====================================
[ [ -1, -1, 2 ], [ -1, 0, 1 ], [ -1, 0, 1 ] ]
====================================

下面还需要去处理一下重复的情况！

/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
   let ret = []
   // 先对数组进行从小到大排序！
   nums = nums.sort((a, b) => a - b); //[ -4, -1, -1, 0, 1, 2 ]
   //注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数，所以全部循环次数只有`num.length-2`）
   for (let i = 0; i < nums.length - 2; i++) {
       let l = i + 1;
       let r = nums.length - 1;
       // 固定了重复的值，跳过！
       if (i > 0 && nums[i] === nums[i - 1]) {
           continue
       }
       while (l < r) {
           if (nums[i] + nums[l] + nums[r] < 0) {
               l += 1
               // 因为排序是从小到大的，如果当前的小于0，那么就让左指针往右移动，找大一点的！
               // 如果跳完了当前和上一个相同那么就多跳一次
               while (l < r && nums[l] === nums[l - 1]) {
                   l += 1
               }
           } else if (nums[i] + nums[l] + nums[r] > 0) {
               // 因为排序是从大到小的，如果当前的大于0，那么就让右指针往左移动，找小一点的！
               r -= 1
               // 如果跳完了当前和上一个相同那么就多跳一次
               while (l < r && nums[r] === nums[r + 1]) {
                   r -= 1
               }
           } else {
               // 如果找到了，那么就存起来，并且同时向内移动一位继续寻找！
               ret.push([nums[i], nums[l], nums[r]])
               l += 1;
               r -= 1;
               //  如果跳完了当前和上一个相同那么就多跳一次
               while (l < r && nums[l] === nums[l - 1]) {
                   l += 1
               }
               // 如果跳完了当前和上一个相同那么就多跳一次
               while (l < r && nums[r] === nums[r + 1]) {
                   r -= 1
               }
           }
       }
   }
   return ret;
};

目录CONTENT

强大的双指针法-leetcode15. 三数之和

评论区