两数之和与哈希表：从暴力O(n²)到O(n)的思维转换

我第一次认认真真刷题，翻开的第一道就是“两数之和”。那时候觉得简单，两层 for 循环套上去，半小时写出代码，还挺得意。后来去面试，面试官把这道题原封不动出给我，我条件反射写了暴力解，他追问了一句“能不能优化到 O(n)”，我当场卡住。现在回头看，这道题挂在“哈希表”这个标签下面，真正要教会我们的不是某个 API 怎么调用，而是一种思维转换：把“在数组里找两个数”变成“在历史记录里查一个数”。这个转换一旦打通，后面很多题都会顺手很多。这篇文章想把哈希表解两数之和这件事讲透，从暴力优化到哈希表选型，从代码顺序到边界测试，再顺手把两数之和衍生的各类变体一起理一遍。无论你是刚接触算法的萌新，还是准备面试想补细节的开发者，这篇文章都可以当作一份比较完整的复盘笔记来看。

1. 题目的真面目：两数之和其实是一道查找题

1.1 暴力解法为什么慢：每次判断都在重头扫数组

题目描述很简单：给定一个整数数组nums和一个目标值target，在数组中找出和为目标值的两个整数，返回它们的下标。

很多人第一反应是暴力枚举：

for (int i = 0; i < nums.size(); ++i) { for (int j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {};

这段代码没有任何逻辑错误，但它的时间复杂度是 O(n²)。为什么慢？慢在内层循环每次都在重新扫描整个数组。

当外层指针走到第 i 个元素时，内层要从 i+1 开始再扫一遍。前面已经遍历过的那些元素，没有被记下来，下一次判断时又得重新问一遍“你和我配不配”。这就像一个丢三落四的人，每次要找一封信都从整个抽屉开始翻，明明上一秒刚看过那封信，下一秒又忘了它放在哪。

暴力解不是“错”，而是“笨”。它没有利用已经扫描过的信息，每次都在做重复劳动。

1.2 转折点：把“找两个数”换成“查一个补数”

题目给了我们一个非常重要的等式：

nums[i] + nums[j] = target

移项之后就是：

nums[j] = target - nums[i]

这个移项看起来平淡无奇，却是整道题的核心转折点。

原本我们思考的是“哪两个数相加等于 target”，这是一种组合式思维，需要两两配对。移项之后，问题变成了：当我站在 nums[i] 面前时，我只想知道一个问题——target - nums[i] 这个“补数”，之前在数组里出现过吗？

“之前出现过吗”本质上是一个查找问题。

数组本身是无序的，线性查找需要 O(n)，于是整个算法又退化到 O(n²)。但如果我们在遍历过程中，把已经看过的每个元素都放进一个查找速度很快的结构里，那么每次判断补数是否出现过，就只需要 O(1) 的平均时间。

这个结构就是哈希表。

1.3 空间换时间的代价与适用条件

用哈希表解两数之和，本质上是典型的空间换时间。

时间复杂度从 O(n²) 降到 O(n)，空间复杂度从 O(1) 涨到 O(n)。我们用了一个“额外抽屉”来装已经见过的数，换来的是每次查询的高效率。

那是不是所有题目都适合这么换？不一定。空间换时间成立的前提是：查询操作足够频繁，且哈希表带来的收益能覆盖额外空间的成本。两数之和显然满足，因为内层循环原本要做 O(n) 次的线性查询，换哈希表后每次查询降到平均 O(1)，收益非常明显。如果问题规模很小，比如数组只有三五个元素，暴力解反而更简单直接，没必要动用哈希表。

这个判断标准，在后文讲变体时还会反复出现。

2. 哈希表选型：为什么必须是“值到下标的字典”

2.1 题目要求返回下标，所以 set 不够用

确定用哈希表之后，第二个问题是：具体用哪种结构？

很多初学者第一次接触这道题时，会想到set，因为set能快速判断一个元素是否存在。但两数之和的要求是返回下标，而不是“是否存在”。

unordered_set只能告诉你“在不在”，没有办法告诉你“在哪个位置”。所以这里需要的是一个“字典”结构，把数组元素的值映射到它的下标：

键（key）：数组元素的值 值（value）：该元素在数组中的下标

在 C++ 里对应unordered_map<int, int>，在 Python 里对应dict，在 Java 里对应HashMap<Integer, Integer>。这个映射关系要记清楚，后面所有讲解都建立在“值到下标”这个语义上。

2.2 unordered_map、map、Python dict 三者怎么选

同样是“字典”，底层实现可能完全不同，选错了会直接影响复杂度。

以 C++ 为例：

• std::unordered_map：哈希表实现，查找、插入的平均时间复杂度 O(1)
• std::map：红黑树实现，查找、插入的时间复杂度 O(logn)

两数之和要求整体 O(n)，所以必须选unordered_map。如果用map，外层循环 n 次，每次查询 O(logn)，总体变成 O(nlogn)，虽然比暴力解好，但没有把哈希表的优势用到位。

Python 的dict在标准实现里就是哈希表，直接用即可。

面试时如果被问到“为什么不用有序的 Map”，原因就在这里：我们只关心“存不存在”和“下标是多少”，并不关心元素之间的相对顺序，不需要引入有序性带来的 O(logn) 成本。

2.3 别把哈希表当成万能钥匙：还看数据特征

哈希表很强大，但它不是所有两数之和问题的唯一答案。

如果题目额外说“输入数组是升序排列的”，那更优解可能是双指针，因为可以利用有序性把空间优化到 O(1)。如果题目要求“找出所有不重复的组合”，哈希表在处理去重时就会变得非常繁琐，很可能不如“排序 + 双指针”来得干净。

这说明：选什么数据结构，取决于题目给了什么条件、限制了什么资源。哈希表只是若干可能性中的一种，不是模板。

3. 标准代码的每一步都在防什么：实现细节拆解

3.1 一份能直接跑的 C++ 和 Python 实现

这是最经典的哈希表解法。先用 C++ 写一遍：

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hash; for (int i = 0; i < nums.size(); ++i) { int complement = target - nums[i]; if (hash.find(complement) != hash.end()) { return {hash[complement], i}; } hash[nums[i]] = i; } return {}; } };

Python 版本逻辑完全一致：

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hash_map = {} for i, num in enumerate(nums): complement = target - num if complement in hash_map: return [hash_map[complement], i] hash_map[num] = i return []

代码看起来很短，但每一行都有讲究。尤其要注意循环体里那条语句的顺序：先查补数，再把当前元素放进哈希表。这个顺序不是随手写的，下面用一个反例说明为什么必须这样。

3.2 先查再插的顺序：一个反例讲清为什么

考虑一个非常简单的例子：

nums = [3, 2, 4] target = 6

正确答案有两个候选：3 + 3不成立，因为 3 只出现了一次；真正成立的是2 + 4，下标是[1, 2]。

如果代码写成“先插入、再查询”，会发生什么？

• i = 0，先把nums[0] = 3插入哈希表
• 然后查补数target - 3 = 3
• 哈希表里已经有刚插入的 3，并且它的下标是 0
• 于是返回[0, 0]

[0, 0]这个答案是错的：下标 0 表示的 3 被当成两个不同元素用了，但数组里这个 3 只有一个。

反过来看标准写法“先查询、再插入”：

• i = 0，查补数 3，哈希表为空，查不到；插入 3
• i = 1，查补数 4，查不到；插入 2
• i = 2，查补数 2，哈希表里有，下标是 1；返回[1, 2]

答案正确。

这个顺序问题的本质是：当前元素还不应该成为自己的“另一半”。只有当它作为“历史元素”被后面的元素查询时，它才配对。所以在把当前元素存入哈希表之前，必须先检查补数是否已经在表里。

3.3 判断“存在”要用接口，别用值判断

还有一个很隐蔽的坑：判断补数是否存在时，不要用“取出来的值是否等于 0”这种方式。

C++ 里有人会这样写：

if (hash[complement] != 0) { return {hash[complement], i}; }

看起来好像没问题，因为下标从 0 开始，如果哈希表里没有这个键，unordered_map的operator[]会返回 0。

但实际上这会翻车。例子：

nums = [2, 1, 4] target = 6

正确答案是[0, 2]，因为2 + 4 = 6。

走一遍错误写法：

• i = 0，插入2，hash[2] = 0
• i = 1，插入1，hash[1] = 1
• i = 2，nums[2] = 4，补数是2
• hash[2]的值是 0，if (hash[complement] != 0)判断为 false，于是漏掉了正确答案

问题就出在下标 0 这个合法值被当成了“不存在”的标记。

所以判断存在性，C++ 用find()，Python 用in，Java 用containsKey()。永远不要用一个可能合法的业务值去兼任“哨兵值”。这个教训在更复杂的工程代码里同样适用。

4. 复盘多年后我才总结出的边界细节

4.1 重复元素与下标覆盖：为什么本题可以“容忍”

数组里可能出现重复元素，例如：

nums = [1, 2, 2, 3] target = 4

如果两个2分别在下标 1 和 2，遍历到第二个2时，hash[2]会被覆盖成 2。之后遍历到3时，补数是 1，哈希表里能找到下标 0 的 1，于是返回[0, 3]，也就是1 + 3 = 4，答案合法。

但如果另一个合法答案2 + 2存在，而1 + 3不存在呢？比如：

nums = [1, 2, 2, 2] target = 4

遍历到最后时，hash[2]保存的是最后一个 2 的下标 3，当前元素是 2，补数是 2，哈希表里有，于是返回[2, 3]，答案同样合法。

为什么覆盖不会导致无解？因为题目只要求返回任意一组答案。只要存在解，遍历到后一个元素时，它的补数一定已经在哈希表里，所以至少能返回一组。这正是“返回任意一对”这个约束带来的宽松空间。

如果题目改成“返回所有可能的组合”，那这个哈希表实现就需要升级为“值到多个下标的映射”，否则会漏解。理解题目约束，比背代码重要得多。

4.2 负数、零和空数组：不要做任何隐含假设

初学者写代码时经常默认数组元素都是正数，或者 target 一定是正数。两数之和的题目里没有这个约束。

看一个例子：

nums = [-3, 4, 3] target = 0

正确解法是-3 + 3 = 0，下标[0, 2]。

哈希表处理负数没有任何额外成本：complement = target - num，本身就能算出负数。真正需要注意的是，不要自己脑补“元素范围大于等于 0”，更不要在代码里写类似if (nums[i] > target) continue;这种“优化”。这个剪枝在全是负数时完全失效，甚至会把正确答案剪掉。

空数组也需要考虑。nums为空时，循环不会执行，直接返回空结果。标准写法天然支持，所以不需要为它写特判，但面试时最好主动提一句“空数组直接返回空”，显得有完备性意识。

4.3 无解时返回什么：代码完备性的分水岭

题目保证有解，所以返回空数组不会在在线评测里触发。但面试时，面试官很可能会追问：如果无解，你的函数返回什么？

C++ 版本最后写了return {};，Python 版本写了return []。这看起来简单，却体现了一个函数是否具备完备性。

这里还想分享一个我自己多年形成的习惯：写完代码后在草稿纸上跑两个用例，一个正常用例，一个专门攻击自己的用例。比如[3, 2, 4]配target = 6，专门用来测试“会不会自己配自己”；[2, 1, 4]配target = 6，专门用来测试“下标 0 是否被误判”。这两个用例能揪出绝大多数隐蔽 bug。

5. 一个哈希表题长出的题型家族

5.1 输入有序的两数之和：用双指针省掉哈希表

两数之和有一个常见变体：输入数组已经按升序排列。这时有更省空间的解法——双指针。

思路很简单：两个指针分别指向数组两端，计算当前和。如果和小于 target，说明需要更大一点的数，左指针右移；如果和大于 target，说明需要更小一点的数，右指针左移。

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

为什么有序情况下双指针可行？因为有序数组给了我们一个“单调性”：左指针往右移，和一定变大；右指针往左移，和一定变小。我们可以根据当前和的偏差，安全地排除一部分搜索空间。这个解法的空间复杂度降到 O(1)，比哈希表更优。

对比两种思路：无序用哈希表，有序用双指针，本质上是“根据数据特征选择最优策略”。

5.2 三数之和为什么不首选哈希：去重成本是主要矛盾

三数之和可以看作两数之和的高维版：固定一个数，剩下的就是一个两数之和子问题。按这个思路，哈希表似乎也能解，但真正动手后会发现——去重太麻烦了。

题目要求返回所有不重复的三元组，不能有重复组合。用哈希表找两数时，很容易找到同一组解多次，需要在三个位置都做去重，代码复杂度急剧上升。排序 + 双指针则能借助有序性，在移动指针的同时自然跳过重复值，实现简单得多。

这个例子特别能说明一个观点：哈希表不是万能的。它擅长“查找”，却不擅长“去重”。遇到组合类题目，先去想数据特征和去重要求，再决定用哪套工具。

5.3 设计一个支持重复数据的 TwoSum：改存出现次数

另一个高频 Follow-up 是设计一个类，支持两种操作：

• add(num)：插入一个数
• find(target)：判断当前集合中是否存在两个数的和等于 target

这个变体和原题最大的区别在于：数据不是一次性给定的，而是动态加入的，并且同一个数字可能出现多次。

哈希表不能只存“值到下标”了，而要存“值到出现次数”：

class TwoSum { private: unordered_map<int, int> count; public: void add(int num) { ++count[num]; } bool find(int target) { for (auto& [num, cnt] : count) { int need = target - num; if (need == num) { if (cnt > 1) return true; } else if (count.count(need)) { return true; } } return false; } };

关键逻辑在第 9 到第 13 行：如果补数等于当前数本身，只有当它的出现次数大于 1 时，才算找到答案。这是原题“不能自己配自己”在设计版中的真正体现。

这个问题经常作为两数之和的追加题出现，考察的是对哈希表“键值语义”的灵活迁移：原题存下标，设计题存计数，结构变了，本质还是用哈希表加速查找。

两数之和这道题，我这些年重写过很多次。从第一次暴力解，到后来熟背哈希模板，再到研究各种变体，最大的体会是：它表面上是数据结构题，实际上是“空间换时间”这一思维在查找问题上的经典示范。如果你正处在刷题初期，建议把这题当成思维模板，把“先查再插”的顺序、用接口判断存在性这两个细节刻进肌肉记忆。等到了面试，面试官无论怎么追问，你都能从原理上接住。最后再分享一个我自己的习惯：每道题我都会在草稿纸上写两个用例，一个正常通过，一个专门攻击自己的代码。比如[3, 2, 4]配target = 6。很多隐蔽的 bug，都是这样在真正上考场之前被提前揪出来的。