手帐 Blog

主题

复盘 · LC 15 三数之和 ​

题目 ​

题意 ​

给定整数数组 nums，找出所有使 a + b + c = 0 的三元组，且不能包含重复三元组（值相同算重复，与下标无关）。

  • 三元组内三个数下标互不相同。
  • 返回列表顺序任意。

边界：全零、大量重复、无解、负数与正数混排、长度 < 3。

涉及算法 ​

标签一句话
排序 + 对撞双指针固定 i，在右侧用 j/k 夹逼找 -nums[i]
去重i、命中后的 j/k 都要跳过相同值

教程对照：05 · 对撞双指针（本篇精讲题）。
补数直觉可回扣：03 · 两数之和。

评价我的解法 ​

两版：先「两数 + Map 查第三个数」超时；再改成教程标准排序对撞，通过。

第一版（超时） ​

我的代码（摘自 15-三数之和/index.js，不含测例）：

javascript
var threeSum = function (nums) {
  const res = new Set();
  const numMap = new Map();
  for (const n of nums) {
    const count = numMap.get(n) || 0;
    numMap.set(n, count + 1);
  }
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (i === j) {
        continue;
      }
      const n1 = nums[i],
        n2 = nums[j];
      if (numMap.has(-n1 - n2)) {
        const n1Count = numMap.get(n1);
        const n2Count = numMap.get(n2);
        const n3 = -n1 - n2;
        if (n3 === n1 && n1Count === 1) {
          continue;
        } else if (n3 === n2 && n2Count === 1) {
          continue;
        } else if (n3 === n1 && n3 === n2 && n1Count <= 2) {
          continue;
        }
        const str = JSON.stringify([n1, n2, -n1 - n2].sort());
        res.add(str);
      }
    }
  }
  return [...res].map((str) => JSON.parse(str));
};

问题很集中：

  1. 双层枚举 i、j → O(n²)×哈希，数据一大就 TLE（注释：312/316 超时）。
  2. 用频次修补「下标冲突」：逻辑绕，且仍没降复杂度；三元组去重靠 JSON.stringify + Set，正确但贵。
  3. 方向感对：三数之和 ≈ 两数之和的补数；缺的是先排序再对撞，而不是在无序数组上硬套 Map。

第二版（排序 + 对撞） ​

我的代码（摘自 15-三数之和/index2.js，不含测例）：

javascript
var threeSum = function (nums) {
  const resArr = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] === nums[i - 1]) {
      continue;
    }
    const item = -nums[i];
    for (
      let j = i + 1, k = nums.length - 1;
      j < k && j < nums.length - 1 && k >= i;
    ) {
      const n1 = nums[j];
      const n2 = nums[k];
      if (n1 + n2 === item) {
        resArr.push([n1, n2, -item]);
        while (j < k && nums[j] === nums[j + 1]) j++;
        while (j < k && nums[k] === nums[k - 1]) k--;
        j++;
        k--;
        continue;
      } else if (n1 + n2 > item) {
        k--;
      } else {
        j++;
      }
    }
  }
  return resArr;
};

对在哪：

  1. 排序 + 固定 i + 对撞：时间 O(n²)，能过。
  2. 命中后 j/k 跳重：全零样例 [0,0,0,0,0] 只出一组，说明去重意识在。

糙在哪：

  1. i 去重写成 nums[i] === nums[i - 1]：i === 0 时靠 undefined 碰巧通过；面试应写成 i > 0 && nums[i] === nums[i - 1]，并常加 nums[i] > 0 早停。
  2. 内层循环条件多余：j < k 已够；j < nums.length - 1 && k >= i 可读性差，易让人以为还有别的不变量。
  3. 三元组顺序 [n1, n2, -item] 与常见的 [nums[i], j, k] 不同，判题不管，口述时固定「从小到大」更稳。

小结：第一版证明「只会 Map 补数」不够；第二版已是 05 篇核心模板。下次默写优先：sort → for i → while j<k → 三处去重。

最佳题解 ​

与终解同套路，补齐早停与清晰去重：

javascript
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const res = [];
  nums.sort((a, b) => a - b);
  const n = nums.length;
  for (let i = 0; i < n - 2; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let j = i + 1;
    let k = n - 1;
    while (j < k) {
      const sum = nums[i] + nums[j] + nums[k];
      if (sum === 0) {
        res.push([nums[i], nums[j], nums[k]]);
        while (j < k && nums[j] === nums[j + 1]) j++;
        while (j < k && nums[k] === nums[k - 1]) k--;
        j++;
        k--;
      } else if (sum < 0) {
        j++;
      } else {
        k--;
      }
    }
  }
  return res;
};
  • 时间 O(n²)，空间 O(1) 额外（不计答案与排序）。
  • 为何更优：排序把「找两数和」变成对撞；去重在指针层完成，不必 Set/JSON。

关联题目 ​

题为何相关
1. 两数之和补数思想的一维版
167. 两数之和 II有序数组上的对撞模板
16. 最接近的三数之和同一骨架，记录最接近
18. 四数之和多固定一层 + 同样去重

一句话带走 ​

三数之和 = 排序 → 固定 i → 对撞找两数和 → i/j/k 去重；别在无序数组上双层枚举硬套哈希。