15.三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

找了很多，这是能稍微看懂的一个，解题思路：githber的解题思路，总体思路为：先进行排序，按照a+b+c=0这个思路，左边的一定是负数或0，固定一个i下标，然后定义first与last分别为i+1与len-1，

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  let res = [] 
  nums.sort((a,b)=>a -b) 
  let len = nums.length 
  // 保证整个数组既有符数又有正数
  if(nums[0] <=0 && nums[len-1]>0) { 
    let i = 0
    while(i<len-2) { 
      if(nums[i] > 0) break;  // 当i到大于0的下标时，则表示以无解
      let first = i + 1
      let last = len - 1 
      while(first<last) { 
        if(nums[i] * nums[last] > 0) break; // 当第一个与最后一个同符号的时候，表示相加肯定大于0 无解
        let sum = nums[i] + nums[first] + nums[last]
        if(sum === 0) { 
          res.push([nums[i],nums[first],nums[last]])
        }
        if(sum<=0) { 
          // 负数过小 左边要向右移一位
          // 重复的值跳过
          while(nums[first] === nums[++first]){}
        } else { 
          // 正数过大 右边要向左移一位
          // 重复的值跳过
          while(nums[last] === nums[--last]) {} 
        }
      }
      while (nums[i] === nums[++i]) {}
    }
  }
  return res
};

console.log(threeSum([4,-10,-11,-12,-8,-12,-14,-11,-6,2,-4,2,3,12,-3,-12,-14,-12,-8,-9,-6,-3,10,2,14,10,7,-7,-9,0,-9,10,-2,-5,14,5,-9,7,9,0,-14,12,10,4,9,-8,8,11,-5,-15,-13,-3,-11,4,14,11,-1,-2,-11,5,14,-4,-8,-3,6,-9,9,12,6,3,-10,7,0,-15,-3,-13,-8,12,13,-5,12,-15,7,8,-4,-2,4,2,3,9,-8,2,-10,-1,6,3,-2,0,-7,11,-12,-2,3,-4,-2,7,-2,-3,4,-12,-1,1,10,13,-5,-9,-12,6,8,7,0,7,-6,5,13,8,-14,-12]));