经典题解析：两数之和，为什么哈希表能把 O(n²) 变成 O(n)

图 1：本文封面，点明题目与核心优化手段。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料（见文末来源说明），与任何公司的当前招聘无关。「两数之和」大概是算法面试里出现频率最高的入门题，但它真正的考点不是会不会做，而是能不能讲清楚复杂度从 O(n²) 降到 O(n) 的那一步是怎么发生的。

想象面试现场，面试官写下题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数，返回它们的下标；每组输入只有一个答案，同一个元素不能用两次。

第一步，审题。

题目里藏着两个关键信息。一是返回的是下标而不是值，排序这类会打乱位置的思路要先排除或改造。二是「只有一个答案」，不用考虑多解去重。真正的考察点在于：你能不能从暴力解出发，指出瓶颈在哪，再给出一个本质更优的结构。

第二步，基础回答：从 O(n²) 到 O(n)。

暴力法谁都写得出：双重循环枚举所有数对，逐个检查是否等于目标值，时间 O(n²)，额外空间 O(1)。瓶颈很明确——对每个数 x，都要把剩下的数全部扫一遍，只为回答一个问题：「target - x 在不在数组里？」

这个问题恰恰是哈希表的主场。把「值到下标」的映射存进哈希表，查询就是 O(1)。于是流程变成：从头到尾只遍历一遍，对每个数 x，先查哈希表里有没有 target - x，有就直接返回答案，没有就把 x 和它的下标放进表里继续走。时间降到 O(n)，代价是 O(n) 的额外空间——这就是「用空间换时间」最标准的教科书样本。

第三步，写出可运行的代码。

下面这份实现包含暴力法与哈希法对照、输入校验和正确性验证，用 Node.js 22.15.0 直接运行（node two-sum.js）即可：

'use strict';

// 暴力法：双重循环，O(n^2) 时间、O(1) 额外空间
function twoSumBrute(nums, target) {
  checkInput(nums, target);
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return null;
}

// 哈希表法：边遍历边记录「值 -> 下标」，O(n) 时间、O(n) 额外空间
function twoSumHash(nums, target) {
  checkInput(nums, target);
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}

function checkInput(nums, target) {
  if (!Array.isArray(nums) || nums.length < 2) {
    throw new TypeError('nums 必须是长度不小于 2 的数组');
  }
  if (!nums.every(Number.isFinite) || !Number.isFinite(target)) {
    throw new TypeError('数组元素与 target 都必须是有限数值');
  }
}

const cases = [
  [[2, 7, 11, 15], 9],
  [[3, 2, 4], 6],
  [[3, 3], 6],
  [[1, 5, 5, 10], 10],
];
for (const [nums, target] of cases) {
  const b = twoSumBrute(nums, target);
  const h = twoSumHash(nums, target);
  console.log(`nums=[${nums}] target=${target} -> 暴力法 [${b}] 哈希法 [${h}]`);
  if (nums[b[0]] + nums[b[1]] !== target || nums[h[0]] + nums[h[1]] !== target) {
    throw new Error('结果校验失败');
  }
}
console.log('无解输入 [1,2,3] target=99 ->', twoSumHash([1, 2, 3], 99));

function bench(fn, nums, target, rounds) {
  const start = performance.now();
  for (let r = 0; r < rounds; r++) fn(nums, target);
  return (performance.now() - start).toFixed(1);
}
const big = Array.from({ length: 10000 }, (_, i) => i * 2);
const bigTarget = big[big.length - 2] + big[big.length - 1];
console.log(`n=10000，暴力法 1 次耗时：${bench(twoSumBrute, big, bigTarget, 1)} ms`);
console.log(`n=10000，哈希法 1000 次耗时：${bench(twoSumHash, big, bigTarget, 1000)} ms`);

实测输出如下（耗时因机器而异，量级不变）：

nums=[2,7,11,15] target=9 -> 暴力法 [0,1] 哈希法 [0,1]
nums=[3,2,4] target=6 -> 暴力法 [1,2] 哈希法 [1,2]
nums=[3,3] target=6 -> 暴力法 [0,1] 哈希法 [0,1]
nums=[1,5,5,10] target=10 -> 暴力法 [1,2] 哈希法 [1,2]
无解输入 [1,2,3] target=99 -> null
n=10000，暴力法 1 次耗时：41.8 ms
n=10000，哈希法 1000 次耗时：224.8 ms

注意最后两行：n 取一万时，暴力法跑一次的耗时，够哈希法跑几百次——单次差距在两个数量级以上。复杂度不是纸面符号，数据规模一放大就全部兑现。

图 2：暴力枚举的 n(n−1)/2 次比较，对比哈希法的一次扫描命中。

第四步，可能的追问。

「返回的是值而不是下标，还能更快吗？」可以先排序再用双指针，O(n log n)，空间比哈希法省，但下标信息丢了。「有重复元素怎么办？」题目保证单解时不用处理；代码里 [3,3] 的例子说明哈希法天然支持同值不同下标。「哈希法一定更好吗？」数组很短时两者无感，常数因子甚至暴力法更省；哈希法的价值体现在规模上。

易错点清单。

一，在同一个元素上自我配对——必须先查表再存入，顺序反了 [3,3] 这种用例会出错。二，返回了值而不是下标。三，只写哈希法、讲不出暴力法的瓶颈，等于跳过了这题真正的考点。四，对无解输入没有约定返回或抛错，边界处理缺失。

回到面试现场，建议的答题节奏：先复述题目确认返回下标与单解约束，再写暴力法并指出瓶颈是「反复查找配对」，然后引出哈希表把查找降到 O(1)，最后主动给出复杂度对比和边界用例。这个节奏展示的是推导能力，而不是背题。

哈希表这种「边遍历边记录」的思想，在 AI 工程里对应着样本去重、特征匹配、KV 缓存查找等大量场景。你还见过哪些题是用同一张「空间换时间」的牌翻盘的？欢迎举例。

参考资料

• Node.js v22.x 官方 API 文档（文中代码运行环境为 Node.js 22.15.0，Map 与 performance.now 行为以此为准） — https://nodejs.org/docs/latest-v22.x/api/