两数之和怎样从 O(n²) 优化到 O(n)？哈希表在算法题里怎么用？

简答

题目是：给一个数组和一个目标值，找出和等于目标值的两个数的下标。最直接的做法是两层循环，把每一对数都加一遍，n 个数要比较大约 n²/2 次，是 O(n²)。

换个角度想：遍历到数字 x 时，我需要的另一个数一定是 target - x。只要能很快知道“之前有没有见过 target - x”，一次遍历就能找到答案。Map 正好能做到，查找和插入平均都是常数时间。所以边遍历边把“数字 → 下标”存进 Map，每一步先查差值，查到就返回，没查到就把当前数存进去。

这样时间降到 O(n)，代价是 Map 要额外占 O(n) 的空间，这叫用空间换时间。很多算法题都是这个思路：把“在前面找某个东西”从一次遍历变成一次查表。

要注意，必须先查再存。如果先把当前数存进去再查，遇到 target 正好是当前数两倍的情况，比如 [3] 找 6，会把同一个元素用两次。

代码实现

function twoSum(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;
}

console.log(twoSum([2, 7, 11, 15], 9).join()); // 0,1
console.log(twoSum([3, 2, 4], 6).join()); // 1,2
console.log(twoSum([3, 3], 6).join()); // 0,1
console.log(twoSum([1, 2], 10)); // null

第二个例子 [3, 2, 4] 找 6，为什么不是 0,0？遍历到下标 0 的 3 时，需要另一个 3，可 Map 还是空的，查不到，于是存进 3 → 0。之后遇到 2，需要 4，没有；存进 2 → 1。遇到 4，需要 2，查到下标 1，返回 [1, 2]。因为先查后存，下标 0 的 3 永远不会和自己配对。

第三个例子 [3, 3] 能找到 0,1，说明重复值也能处理：第一个 3 存进去，第二个 3 来查时正好找到它。

为什么用 Map 而不是普通对象

普通对象的键会被转成字符串，数字 1 和字符串 '1' 会被当成同一个键，还可能和原型上的属性名冲突，比如 'constructor'。Map 的键可以是任何值，按 SameValueZero 规则比较，也没有原型属性干扰。只需要判断“有没有出现过”时，用 Set 就够了。

常见追问

如果数组是有序的，有没有不用额外空间的做法？

有，用左右双指针。左指针从头、右指针从尾，两数之和小于目标就左指针右移，大于目标就右指针左移，相等就找到了。时间 O(n)，空间 O(1)。

哈希表还能解哪些常见题？

判断字符串是不是字母异位词，就是统计每个字符出现的次数再比较；找数组里第一个不重复的元素、统计出现频率最高的元素，也都是先用 Map 计数。