1. 三数之和（15）

一、题目内容 中等

给你一个包含 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

  二、解题思路

  双指针动画如下：
  
  要找出 a + b + c = 0，那么其实就是找 b + c = —a 。
  我们遍历 nums，即 视 a 为 nums[i]，所谓双指针 left、right 分别指代 b、c。
  我们指针移动，肯定要按照某些规则，判断符不符合条件，来决定移动方向。
  在这里，这种规则，其实就很自然想到，给数组排个序，这样可以按大小顺序来移动指针。
  我们以[-1,0,1,2,-1,-4]来举例，先排个序，[-4,-1,-1,0,1,2]。

1. 首先，我们 a = nums[0]，left = nums[1]，right = nums[5]。其中 a 固定的，left、right 可移动
   1. a + left + right < 0，说明 left 太小了，要向右移动
   2. a + left + right > 0，说明 right 太大了，要向左移动
   3. a + left + right = 0，那就舒服了，是结果的一种
2. 接着，我们 a = nums[1]，left = nums[2]，right = nums[5]。继续判断

3. 同理，一直到 a = nums[5]。其实到 nums[4] 就可以停止了，只剩下两个元素，没比较的必要。

   1. 要用就是，其实当 a > 0时，也可以停止比较了，因为三个加起来必定大于 0，不符合题意

      三、具体代码

      ```javascript /**
   • @param {number[]} nums

   • @return {number[][]} */ var threeSum = function (nums) { nums.sort((a, b) => a - b) const result = [] for (let i = 0, len = nums.length; i < len; i++) { if (nums[i] > 0) break if (nums[i] === nums[i - 1]) continue

     let left = i + 1, right = len - 1

     while (left < right) { if (nums[i] + nums[left] + nums[right] < 0) { while (left < right && nums[left] === nums[left + 1]) left++ left++ } else if (nums[i] + nums[left] + nums[right] > 0) { while (left < right && nums[right] === nums[right - 1]) right— right— } else { result.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— } } } return result }; ```

     四、其他解法