【JS算法】三数之和

15题：数组中找出a + b + c = 0的3个数

解题思路

1、选排好序
2、for循环从第一个数开始（如2）：那就需要找2个数，且他两的和是-2
3、while循环然后双指针跑 => <=，左右2值相加大于目标值，则右边继续<=; 小于则左边继续=>
4、两指针相遇，则本次while结束

var threeSum = function (nums) {
  if (nums.length < 3) {
    return [];
  }
  let list = [];
  nums.sort((a, b) => a - b); //先排好序
  //console.log("nums:", nums);

  for (let i = 0; i < nums.length; i++) {
    //相同就跳过这一次循环，因为已经结果过一次了
    if (nums[i] === nums[i - 1]) {
      continue;
    }
    let left = i + 1;
    let right = nums.length - 1; //最后一位，指针从0开始，所有减1

    while (left < right) {
      if (nums[left] + nums[right] + nums[i] === 0) {
        //命中
        list.push([nums[left], nums[right], nums[i]]);
        //准备继续找
        while (nums[left] === nums[left + 1]) {
          //这里是避免相同的值，直接跳过
          left++;
        }
        while (nums[right] === nums[right - 1]) {
          //这里是避免相同的值，直接跳过
          right--;
        }
        //继续找
        left++;
        right--;
      } else if (nums[left] + nums[right] + nums[i] > 0) {
        //数字大了需要，右指针向左前进1
        right--;
      } else {
        //数字小了，需要左指针向右前进1
        left++;
      }
    }
  }
  return list;
};