三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存三个元素 a, b, c，使得 a + b + c = 0
请你找出所有和为 0 且不重复的三元组

最简单的方法是把数组 nums 所有可以三元组的可能都列出来进行循环把和为 0 得取出来并进行去重。
这样的时间复杂度是

更优的解法是先进行排序，再使用双指针的办法进行判断三数之和。这样的时间复杂度是

let nums = [-1, 0, 1, 2, -1, -4, 1, 2]; // [[-4, 2, 2], [-1, -1, 2], [-1, 0, 1]]
var threeSum = function (nums) {
  let resArr = [];
  // 数组至少要有三个元素才能进行
  if (nums.length < 3) return [];
  // 让数组排序，成为一个升序数组 [ -4, -1, -1, 0, 1, 1, 2, 2 ]
  nums = nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    // 开始遍历或当前遍历的数组元素与上一次遍历的数组元素不一样时
    if (i == 0 || nums[i] != nums[i - 1]) {
      // 元素大于 0 时，左右指针的元素都大于 0，无法三数之和等于 0
      if (nums[i] > 0) {
        break;
      }
      // 左指针为当前元素的下个元素，右指针为数组最后一个元素，得出它们对应的索引
      let left = i + 1,
        right = nums.length - 1;
      // 左指针的索引一定要比右指针的索引小
      while (left < right) {
        // 当前元素、左指针元素、右指针元素三数之和为 0
        if (nums[i] + nums[left] + nums[right] == 0) {
          resArr.push([nums[i], nums[left], nums[right]]);
          left++;
          // 左指针右移，直到左指针与前一个左指针的元素不一样或与右指针索引相同
          while (left < right && nums[left] == nums[left - 1]) {
            left++;
          }
        // 三数之和小于 0， 需要多一点的正数，左指针向右移动
        } else if (nums[i] + nums[left] + nums[right] < 0) {
          left++;
          // 左指针右移，直到左指针与前一个左指针的元素不一样或与右指针索引相同
          while (left < right && nums[left] == nums[left - 1]) {
            left++;
          }
        // 三数之和大于 0， 需要多一点的负数，右指针向左移动  
        } else if (nums[i] + nums[left] + nums[right] > 0) {
          right--;
          // 右指针左移，直到右指针与前一个右指针的元素不一样或与左指针索引相同
          while (left < right && nums[right] == nums[right + 1]) {
            right--;
          }
        }
      }
    }
  }
  return resArr;
};
console.log(threeSum(nums));