【JS】数组中相加和为0的三元组

先确定一个数，然后第二个数用一个指针从前到后遍历，第三个数用一个指针，从后到前遍历；

计算结果，然后去重。

去重的核心思想是判定下一个数是否跟当前的数一致，一致则跳过。当然，前提是不能越界。

/**
 * 
 * @param num int整型一维数组 
 * @return int整型二维数组
 */
function threeSum(num) {
  let res = [];
  // 先排序
  num.sort((a, b) => a - b);
  let len = num.length;
  // console.log(JSON.stringify(num), len);
  // 先确定一个数
  for (let i = 0; i < len - 2; i++) {
    // 第二个数，方向往后面移动
    let head = i + 1;
    // 第三个数，方向往前面移动
    let tail = len - 1;
    // 相遇判定，退出条件
    while (head < tail) {
      let sum = num[i] + num[head] + num[tail];
      // 如果结果太大，尾部收缩
      if (sum > 0) tail--;
      // 如果结果太小，头部推进
      else if (sum < 0) head++;
      // 相等则写入结果并去重
      else {
        res.push([num[i], num[head], num[tail]]);
        // 头部去重（如果后面一个数跟当前的数字相等，则代表有重复的结果生成，跳过）
        while (head + 1 < tail && num[head + 1] === num[head]) head++;
        // 尾部去重（如果前面一个数跟当前的数字相等，则代表有重复的结果生成，跳过）
        while (tail - 1 > head && num[tail - 1] === num[head]) tail--;
        // 继续往后推进
        head++;
        // 继续往前推进
        tail--;
      }
    }
    // 为什么是 < len - 2 是因为最少要三个数组合
    while (i < len - 2 && num[i + 1] === num[i]) i++;
  }
  return res;
}
module.exports = {
    threeSum : threeSum
};