leetcode #15 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

• 题目大意
  给定一组整数，找到数组中所有相加等于0的3个数，结果中不能有相同的一组。

其实基本算法就是简单的枚举，可以做少量的优化。
首先我们将数组从小到大排序，从最小的开始扫描。 跳过与之前相同的数字（已经扫描过了），接下来，再剩余的数字中找到另外两个数使他们3个的和为0。 这里，剩余的数字指的是当前数字之后的数字，因为之前的数字所有可能已经被找到了。在找另外两个数字的时候，用两个指针，一个指向剩余数字中最小的，一个指向剩余数字中最大的。当三个数的和超过0时，将指向最大的数字指针向前移动（使数字更小），反之将小指针向后移动。注意跳过相同的数字！

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  console.log(nums);
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] === nums[i - 1]) { // 跳过相同的值
      continue;
    }
    let j = i + 1;
    let k = nums.length - 1;
    const rest = -nums[i];
    while (j < k) {
      if (nums[j] + nums[k] === rest) {
        result.push([nums[i], nums[j], nums[k]]);
        while (j < k && nums[j] === nums[j + 1]) j++; // 跳过相同的值
        while (j < k && nums[k] === nums[k - 1]) k--;
        j++;
        k--;
      } else if (nums[j] + nums[k] > rest) k--; // 如果两数相加比剩余的值大，减小较大的值
      else {
        j++; // 否则增加较小的值
      }
    }
  }
  return result;
};