三数之和

[king-lxt]

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 示例 2：

输入：nums = [] 输出：[] 示例 3：

输入：nums = [0] 输出：[]

[king-lxt]

双指针解题思路

1、我们首先将数组排序
2、对数组进行遍历，取当前遍历的数nums[i]为一个基准数，遍历数后面的数组为寻找数组
3、在寻找数组中设定两个起点，最左侧的left(i+1)和最右侧的right(length-1)
4、判断nums[i] + nums[left] + nums[right]是否等于0，如果等于0，加入结果，并分别将left向右和right向左移动一位
5、如果结果大于0，将right向左移动一位，向结果逼近， 如果小于0 则left 向右移动一位。知道left 不在 小于right

var threeSum = function (nums) {
    const results = [];
    // 对数组排序
    nums.sort((a, b) => a - b);
    if (nums[0] > 0) return results;
    for (let i = 0; i < nums.length; i++) {
        // 跳过重复数字
        if (i && nums[i] === nums[i - 1]) { continue; }
        // 使用双指针
        // 左指针
        let left = i + 1;
        // 右指针
        let right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                // 此处的值 = 0；
                results.push([nums[i], nums[left++], nums[right--]]);
                // 跳过重复数字
                while (nums[left] === nums[left - 1]) {
                    left++;
                }
                // 跳过重复数字
                while (nums[right] === nums[right + 1]) {
                    right--;
                }
            }

        }
    }
    return results;
};

[king-lxt]

const threeSum = function (nums) {
  let set = new Set() // 使用 Set() 
  let result = []
  nums.sort((a, b) => (a - b))

  for(let i =0; i < nums.length - 2; i++) {
    while (nums[i] === nums[i - 1]) {i++} // 去重
    // 第一个数
    let first = nums[i]
    let j = i + 1
    while (j < nums.length) {
      // 第三个数
      let second = 0 - nums[j] - first
      let third = nums[j]

      if(set.has(second)) {
        result.push([first, second, third])

        set.add(third)
        j++

        while (nums[j] === nums[j-1]) {j++} // 去重
      } else {
        set.add(third)
        j++
      }
    }
    set = new Set()
  }
  return result
};