0015-三数之和.md

给你一个包含 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] 输出：[]  

提示：

0 <= nums.length <= 3000 -105 <= nums[i] <= 105

var threeSum = function(nums) {
  nums = nums.sort((a, b) => a - b)
  const arr = []
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) {
      break
    }
    if (nums[i] === nums[i - 1]) {
      continue
    }
    let left = i + 1, right = nums.length - 1
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right]
      if (sum === 0) {
        arr.push([nums[i], nums[left], nums[right]])
        while (left < right && nums[left] === nums[left + 1]) {
          left++
        }
        while (left < right && nums[right] === nums[right - 1]) {
          right--
        }
        left++
        right--
      } else if (sum < 0) {
        left++
      } else if (sum > 0) {
        right--
      }
    }
  }

  return arr
};

解题思路: 想不出来，直接看的题解，发现可以使用排序后双指针来进行操作，一些特殊场景需要排除

• nums[i] > 0 说明已经不可能三数之和为0了直接break
• nums[i] === nums[i - 1] 会导致重复直接continue
• nums[left] === nums[left + 1] 与 nums[right] === nums[right - 1] 的情况都会算作重复需要进行跳过
• arr 新增三数集合后直接 left++ right--， 因为这两端的数必须都变化加上nums[i]才可能等于0
• 如果sum小于0则说明需要加大正数 left++
• 如果sum大于0则说明需要减少正数 right--