[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]

输出：[]

这道题是1.Two Sum的升级版，需要三个数的和为 0。那么我们可以想到，这三个数中的最小数必定为负数，并且另两个数的和等于这个数的相反数。

因此我们需要对数组从小到大进行排序，之后遍历一遍数组，每次固定住最小的那个数字nums[i]，将它的相反数作为 target。

之后的解法就与Two Sum的解法完全一致了，使用首尾指针，由于另外两个数一定比最小数大，因此首次循环首尾指针范围在当前位置i+1到数组尾。

根据以上推导的结论，若这个nums[i]>0，或者尾指针指向的数字<0，则可以直接结束循环了。

跟Two Sum稍有不同的是，当找到 target 的一组解后不能立即结束循环，因为有可能存在多组和为 target 的解。并且数字组成完全相同的解不能放入结果中，需要做好去重操作。

function threeSum(nums: number[]): number[][] {
  nums = nums.sort((a, b) => a - b);

  const res: number[][] = [];
  for (let i = 0; i < nums.length - 2; i++) {
    const min = nums[i];

    // 如果数组的最小值都>0，则一定不存在 a + b + c = 0
    if (min > 0) break;
    // 去掉重复情况
    if (i > 0 && min === nums[i - 1]) continue;

    const target = 0 - min;
    // 接下来就是 2Sum 问题了
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      if (nums[left] + nums[right] === target) {
        res.push([min, nums[left], nums[right]]);
        // 去除重复情况
        while (left < right && nums[left + 1] === nums[left]) left += 1;
        while (left < right && nums[right - 1] === nums[right]) right -= 1;

        // 指针移动到下一组情况
        left += 1;
        right -= 1;
      } else if (nums[left] + nums[right] > target) {
        right -= 1;
      } else {
        left += 1;
      }
    }
  }
  return res;
}