算法-三数之和

肝算法第一天

题目

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

// eg: list: [-1, 1, -2, 0] target: 0
// 输出: [-1, 0, 1]

原题传送门

思路

可仿照两数之和暴力三层遍历，最后去重处理，但无意义

• 指针查数

  选取一个数固定住(例如第一个),选择第二个和最后一个数，作为指针 left right, left++ 和 right–，不断循环找到结果

• 数组排序

  原数组排序后，更适合双指针确定范围并查询

  const list = [-2, -1, 0, 1, 2];
  const target = 0;
  
  /**
    -2 | -1 2 (-1 + 2 小于 0 - -2， 所以 left 指针++)
    -2 | 0 2 返回 [-2, 0, 2] 
    -1 | 0 2 (0 + 2 大于 0 - -1， 所以 right -- )
    -1 | 0 1 返回 [-1, 0, 1]
    0 | 1 2 到头了弟弟
  */

如此思路开始构造函数

function sumThreeNum(list, target) {
    const sl = list.sort((a, b) => a - b);
    const res = [];

    for (let i = 0, len = list.length; i < len; i++) {
        const curr = sl[i];
        const st = target - curr; // st subTarget
        let l = i + 1;
        let r = len - 1;

        // 因为是排序后的数组，所以后面必然比目标大
        if (curr > target) break;

        // 避免当前固定数 与上次固定数一样
        if (i === 0 || sl[i - 1] !== curr) {
            while (l < r) {
                /**
          核心逻辑 
          若左右之和等于子目标 则输出
          若左右之和小于子目标 则 left 指针进一位
          若左右之和大于子目标 则 right 指针减一位
          靠指针缩进范围查询
        */
                if (sl[l] + sl[r] === st) {
                    res.push([sl[i], sl[l], sl[r]]);

                    // 避免下个指针数值和当前数值一样
                    while (l < r && sl[l + 1] === sl[l]) l++;
                    while (l < r && sl[r - 1] === sl[r]) r--;

                    l++;
                    r--;
                } else if (sl[l] + sl[r] < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }
    }

    return res;
}

要记住双指针的解法