从三数之和看优化算法的探索路线

在算法学习中，我们经常遇到这样的困扰：能看懂别人的代码，但很难独立想出类似的思路。LeetCode 第 15 题“三数之和”就是一个典型例子。它的最优解在结构上看似巧妙，很多人会直接记住代码，但忽略了更重要的——如何从零推导出这样的思路。

本文将以“三数之和”为起点，完整还原从暴力解到最优解的思维过程，并展示一套可迁移的“优化路径”，帮助你建立真正的算法感知能力。

问题描述

给定一个整数数组 nums，要求找出所有不重复的三元组 (a, b, c)，使得：

a + b + c = 0

注意：

• 三个数不能重复使用同一个下标
• 结果中不能包含重复的三元组

Step 1：从暴力解出发（时间复杂度 O(n³)）

最直接的方式是三重嵌套循环，枚举所有三元组：

for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    for (let k = j + 1; k < nums.length; k++) {
      if (nums[i] + nums[j] + nums[k] === 0) {
        // 收集三元组
      }
    }
  }
}

虽然可以得到正确答案，但时间复杂度为 O(n³)，在实际使用中效率极低。

关键问题：如何减少枚举的次数？有没有可能只枚举部分元素？

Step 2：固定一位，转化为“两数之和”问题（O(n²)）

如果我们先固定一个数 a = nums[i]，问题就变成了在剩下的数组中找出两个数 b 和 c，满足：

b + c = -a

也就是说，“三数之和”变成了“在数组的子区间中找出两个数，其和为一个目标值”的问题，这正是经典的“两数之和”。

这一步是关键的结构性转化，使得时间复杂度从 O(n³) 降为 O(n²)。

Step 3：在子数组中寻找两数之和（哈希表 vs 双指针）

常见方法是使用哈希表：

let seen = new Set();
for (let j = i + 1; j < nums.length; j++) {
  let complement = -nums[i] - nums[j];
  if (seen.has(complement)) {
    // 找到一组
  }
  seen.add(nums[j]);
}

该方法时间复杂度为 O(n)，加上外层循环总复杂度为 O(n²)。缺点是空间复杂度较高，且处理重复三元组比较麻烦。

更进一步的思考是：如果数组是有序的，是否可以用双指针来优化查找和去重？

Step 4：排序 + 双指针（结构性优化）

将数组排序后，我们可以使用双指针从左右两端向中间逼近，寻找两个数的和是否等于目标值 -a。

整体思路如下：

1. 对数组进行排序，时间复杂度 O(n log n)
2. 枚举第一个数 nums[i]，跳过重复值
3. 使用左右指针 left 和 right，在子区间内寻找匹配的两个数
4. 在找到满足条件的三元组后，继续跳过重复值以防止结果重复

代码实现如下：

nums.sort((a, b) => a - b);

for (let i = 0; i < nums.length - 2; i++) {
  if (i > 0 && nums[i] === nums[i - 1]) continue;

  let left = i + 1, right = nums.length - 1;

  while (left < right) {
    let sum = nums[i] + nums[left] + nums[right];

    if (sum === 0) {
      result.push([nums[i], nums[left], nums[right]]);
      while (left < right && nums[left] === nums[left + 1]) left++;
      while (left < right && nums[right] === nums[right - 1]) right--;
      left++;
      right--;
    } else if (sum < 0) {
      left++;
    } else {
      right--;
    }
  }
}

最终的时间复杂度依然为 O(n²)，但：

• 空间复杂度仅为 O(1)
• 去重处理更为自然
• 结构清晰，逻辑易懂

这就是“三数之和”问题的最优解法。

Step 5：总结优化思路路径

我们可以总结如下的优化路径：

Step 1：三重循环暴力解（O(n³)）
↓
Step 2：固定一位，转为“两数之和 = -a”（O(n²)）
↓
Step 3：两数之和 → 哈希表 or 双指针
↓
Step 4：排序后使用双指针 → 实现结构性优化
↓
Step 5：自然去重、空间最优，得到最终解法（O(n²), O(1)）

从这个过程中可以看出，高效解法并不是突发奇想，而是一步步推导和重构的结果。

进阶思考：两数之和也可以使用双指针实现 O(n)

许多人习惯用哈希表解决“两数之和”问题，但如果数组已排序，使用双指针其实更高效、空间更优：

function twoSumSorted(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    let sum = nums[left] + nums[right];
    if (sum === target) return [nums[left], nums[right]];
    else if (sum < target) left++;
    else right--;
  }
}

该算法时间复杂度为 O(n)，空间复杂度为 O(1)，结构简洁，效率更高。

当然，对于力扣第一题的两数之和中元素本是无序的情况，如果直接排序会打乱原数组的索引，此时如果一定要使用双指针法，可以使用 const arr = nums.map((val, idx) => [val, idx]); 给每个值打上原始位置的标签。力扣两数之和如果使用双指针法，由于进行了排序，时间复杂度会变为 O(nLogn)。

哈希法善于快速定位值与索引的关系，适用于对下标敏感、目标值唯一确定的问题，如 Two Sum。 双指针法善于在有序数组中压缩搜索空间，更适合多数值组合的情况，如 Three Sum、Four Sum，尤其适用于需要避免重复组合的场景。

建议的训练方法

为了具备独立推导这类解法的能力，建议你在日常刷题中遵循以下步骤：

1. 从暴力法开始写起：先解出正确性，再优化效率。
2. 关注重复计算：寻找是否存在“固定部分”或“重复结构”。
3. 尝试结构性转化：如“固定一位”→“转为子问题”。
4. 构建优化工具箱：熟练使用排序、哈希表、双指针、滑动窗口等常见技巧。
5. 总结推导过程：把一题背后的优化路径复盘成笔记。

附加笔记：关于 sort() 我们需要知道的

在 JavaScript 里，sort() 是数组对象的一个内置方法，其主要功能是对数组元素进行排序。基础用法

若不传入参数，sort() 会按照 Unicode 编码的顺序对元素进行排序，排序时会先将元素转换为字符串。

const fruits = ['apple', 'banana', 'cherry', 'date'];
fruits.sort();
console.log(fruits); // 输出: ['apple', 'banana', 'cherry', 'date']

需要注意的是，若直接对数字数组排序，可能会得到不符合预期的结果。

const numbers = [10, 5, 8, 1, 2];
numbers.sort();
console.log(numbers); // 输出: [1, 10, 2, 5, 8]

这是因为 sort() 默认将元素转换为字符串后再比较，所以 "10" 会排在 "2" 之前。

自定义排序规则

若想实现自定义排序，比如按数字大小排序，就需要给 sort() 传入一个比较函数。该函数要返回一个数值，用于指示两个元素的相对顺序。

比较函数的形式为 function(a, b) {...} ，其返回值规则如下：

• 若返回值小于 0，则a会排在b前面。
• 若返回值等于 0，则a和b的相对位置保持不变。
• 若返回值大于 0，则a会排在b后面。