# 三数之和

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

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

function threeSum(nums) {
  var newNums = [];
  var resNums = [];
  // 因为三数之和为0，一定有个数为负数，先排序
  nums.sort((a, b) => a - b);

  for(var i=0; i<nums.length;i++){
    if(nums[i] > 0) {
      break;
    }
    // 如果两个数字相同，直接跳转到下一个循环
    if(i > 0 && nums[i] == nums[i - 1]) {
      continue;
    }
    // 另外j,k两数之和target
    var target = 0 - nums[i];
    var j = i + 1;
    var k = nums.length - 1;

    while(j < k) {
      // 找到后面的两个与nums[i]对应的数字
      if(nums[j] + nums[k] == target) {
        newNums.push(nums[i]);
        newNums.push(nums[j]);
        newNums.push(nums[k]);
        resNums.push(newNums);
        newNums = [];
        // 如果两个数字相同，跳到下一个循环
        while(j < k && nums[j] == nums[j+1]) {
          j = j + 1;
        }

        // 如果两个数字相同，跳到下一个循环
        while(j < k && nums[j] == nums[k+1]) {
          k = k - 1;
        }

        // 否则就往中间靠拢
        j = j + 1;
        k = k - 1;
      } else if (nums[j] + nums[k] < target) {
        // 如果后面两数相加小于target，说明左边还得往右移
        j = j + 1
      } else {
        // 如果后面两数相加大于target，说明右边就要往左移
        k = k - 1
      }
    }
  }
  return resNums;
};