15. 三数之和

https://leetcode-cn.com/problems/3sum/

原题

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

题目分析

因为前面已经做过两数之和，使用了暴力破解。如果这道题还是用暴力破解的话，那就是三层循环，记录下来去重，时间复杂度是 o(n^3)。

那优化一下，这道题可以看作是两数只和的扩展，三数就可以看作是固定一个数，去寻找两数之和等于 0 - 固定数值 的过程。那固定住一个数之后，找另外两个数是否可以优化呢？那就可以利用数组排序了，加上双指针。

比如数组 [ -1, 0, 1, 2, -1, -4 ]。

我们先对其进行排序，排序后的结果为:

然后我们先固定住 -4，然后寻找后面的数中有没有两个数和为 0 - (-4) = 4 的值。那怎么寻找呢？因为我们已经经过排序了，所以可以使用双指针，left 剩下的数值中的最小值，right 指向最大值。如果 left 的值已经大于 4 的话，就说明右侧最小的值都比 4 大，所以肯定就没有两个数的和为 4 了；同理，如果 right 的值已经小于 4 的话，说明最大的值都比 4 小，不可能有加和等于 4 的两个数了；如果 left + right 大于 4 的话，说明 right 的值太大了，right 指针就需要往左移；如果 left + right 小于 4 的话，说明 left 的值太小了，left 指针就需要往右移。

那因为 left + right = -1 + 2 = 1 < 4，left 右移动。

因为数组已经经过排序，所以相同的数值是排在一起的，当指针移动到下一位时，如果跟上一位数值相同，则可以继续移动，因为题目需要去掉重复。所以 left 可以继续右移。

那因为 left + right = 0 + 2 = 2 < 4，left 右移动。
那因为 left + right = 1 + 2 = 3 < 4，left 右移与 right 重合说明没有和为 4 的两个数。
于是我们固定 -1，寻找加和为 1 的两个数。

那因为 left + right = -1 + 2 = 1 === 1，说明 -1，-1，2 这三个元素就是我们要找的加和为 0 的三个元素。继续寻找还有没有加和为 1 的两个数，left 右移，right 左移。

哎，我们 left + right = 0 + 1 = 1 === 1，说明 -1，0，1 也是我们要找的元素。
如此循环查找下去，就能找到所有的三数之和为 0 的结果。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = (nums) => {
  if (nums.length < 3) return []
  const orderNums = nums.sort((a, b) => a - b)
  const ret = []
  for (let i = 0; i <= orderNums.length - 3; i++) {
    if (nums[i] > 0) break // 如果当前元素大于0，则之后的数都大于0，没有加和为0的三个数
    if (orderNums[i] === orderNums[i - 1]) continue
    let j = i + 1;
    let k = orderNums.length - 1
    const sum = 0 - orderNums[i]
    while (j < k) {
      if (orderNums[k] === orderNums[k + 1] && orderNums[j] === orderNums[j - 1] && j - 1 > i) {
        j += 1
        k -= 1
        continue
      }
      if (orderNums[j] + orderNums[k] === sum) {
        ret.push([orderNums[i], orderNums[j], orderNums[k]])
        j += 1
        k -= 1
      } else if (orderNums[j] + orderNums[k] < sum) {
        j += 1
      } else if (orderNums[j] + orderNums[k] > sum) {
        k -= 1
      }
    }
  }
  return ret
}