两数之和LeetCode 开篇第一题也是无数人算法面试的第一次。我刚开始刷题时也瞧不上它——一个双重循环就能过的题有什么好讲的后来我把这道题翻了四五遍在面试里被面试官顺着它连续追问了两数之和 II、三数之和才彻底明白它为什么能常年霸榜热门 100 题的首页它把一个最核心的算法思想——空间换时间用最朴素的方式讲清楚了。这篇博文不整玄乎的套路就是把我自己从暴力解、两遍哈希、一遍哈希一路改过来的过程加上踩过的坑、测试用例设计、面试变体完整复盘一遍。适合刚开始刷 LeetCode 的同学也适合准备面试、想系统过一遍基础题的朋友。1. 题目拆解与暴力解法1.1 先把题目翻译成人话给定一个整数数组 nums 和一个整数 target要求找出数组中和等于 target 的两个整数返回它们的下标。题目带着几个隐含条件每种输入只对应一个答案数组中的同一个元素不能用两次返回顺序随意。这里有几个容易被忽略的点。第一个是同一个元素不能用两次这句话在暴力解里天然满足因为 i 永远不等于 j但在哈希解法里如果你先建表再查询第二遍遍历时需要检查查到的下标是否等于当前下标否则会出现自己加自己的情况。第二个是题目保证了只有一个答案这意味着你不需要处理多个答案的情况但代码里仍然要写优雅的退出逻辑。第三个是返回顺序随意这一点对初学者很友好但后续变形题经常把条件改成要求按升序返回或返回全部组合那时候再调整代码就要重新适应。还有一个大前提值得反复确认数组是无序的。题目没有说输入有序所以你不能直接用双指针从两头夹逼。很多人一上来就写双指针是因为看多了两数之和 II 的题解直接把有序数组的杀手锏用错了地方。拿到题目第一件事永远是看输入条件而不是背解法这个习惯从第一题就要养好。1.2 暴力解法先跑通再谈优化第一次看到这个题最直接的思路就是双重循环def two_sum_brutal(nums, target): n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []这里 j 从 i1 开始有两个好处省掉一半重复比较也天然避免了 ij 的判断。我把这个解法称为及格解。面试时先给这个回答能证明你具备最基础的逻辑和枚举能力但给完一定要主动补一句这个解法时间复杂度是 O(n²)还可以优化到 O(n)。主动暴露优化点比等面试官来追问要好得多这是我在真实面试里学习到的一个沟通经验。暴力解法的问题在数据量变大时立刻暴露。假设数组有 10 万个元素内层循环最坏要跑约 50 亿次比较。我算过这笔账n(n-1)/2 99999 × 100000 / 2 ≈ 5 × 10^9 次。以普通笔记本每秒跑 10^9 次简单操作估算也要几十秒才能出结果。真实业务里谁会等几十秒就为了返回两个下标所以暴力解只能作为保底方案绝不能止步于此。提示面试时如果先写了暴力解一定要主动说出这个可以优化到 O(n)而不是等面试官追问。这是证明你有复杂度意识的最佳时机。1.3 复杂度账本为什么 O(n²) 不够用复杂度的计算看循环嵌套。外层循环 n 次内层循环平均 n/2 次总操作量正比于 n²/2所以时间复杂度是 O(n²)。空间复杂度是 O(1)因为只用了循环变量和常数个临时变量。这里我想多说一句很多新手只背暴力解是 O(n²)却不理解面试官为什么总要追问。实际工作中给定一批数据找配对的场景非常多订单匹配、优惠券配对、日志关键词关联、用户画像标签合并本质都是查找某个东西是否存在、在哪。一旦你掌握查补数的思维而不是停留在两层循环求和就能把这一整类问题统一到一个框架下。这也就是两数之和作为第一题真正的价值——它不是一个孤立的题目而是一类问题的母题。2. 哈希表解法空间换时间的经典示范2.1 为什么选哈希表从找数字到查字典暴力解慢在每次都要把数组从头到尾扫一遍去找补数。理想情况下我们希望拿到一个数字 num 之后能以 O(1) 的速度知道 target - num 在不在数组里、在哪个位置。哈希表字典就是为这个需求量身定做的。哈希表的核心原理可以理解成查字典你想知道苹在第几页不需要从第一页翻起而是直接到拼音索引里定位。数组的索引是连续整数哈希表则通过哈希函数把任意整数映射到存储槽位平均查找时间是 O(1)。Python 里是 dictC 里是 unordered_mapJava 里是 HashMap。空间换时间这句话我们听得多了但它到底换的是什么这里明确一下拿出额外的 O(n) 内存换掉原来的 O(n²) 时间。工程里的缓存系统就是同一逻辑——把热点数据放内存避免每次都查数据库两次遍历的优化不过是在一个更微观的层面复用了同样的智慧。想明白这个类比你以后设计系统方案时也会更有意识地去权衡时间和空间。2.2 两遍哈希先建表再查询两遍哈希的流程非常直观。第一遍遍历数组把所有数字和下标装进哈希表键是数字值是下标。第二遍再遍历数组对每个数字 num 计算 complement target - num去哈希表里查 complement。def two_sum_two_pass(nums, target): hash_map {} for i, num in enumerate(nums): hash_map[num] i for i, num in enumerate(nums): complement target - num if complement in hash_map and hash_map[complement] ! i: return [i, hash_map[complement]] return []注意第二遍必须加上 hash_map[complement] ! i 这个判断因为同一个元素不能用两次。举个具体例子nums [2, 4, 2]target 4。第一遍建表后键 2 对应下标 2后面的覆盖了前面的键 4 对应下标 1。第二遍走到 i0 的 2 时complement 也是 2哈希表里能找到键 2位置 2 不等于当前下标 0所以返回 [0, 2]两个不同位置的 2 相加等于 4正确。如果去掉下标检查就可能返回 [0,0]直接踩了同一元素用两次的红线。我之所以把先建表再查询拆开讲是因为它把两个阶段分得很清晰初学者能一眼看出哈希表扮演的角色。但实际面试时我一般直接写一遍哈希代码更短思路也更优雅接下来就说它。2.3 一遍哈希边查边存的核心技巧一遍哈希的精髓在于边查边存它把两遍哈希压缩成一遍遍历。对每个数字 num先检查 target - num 是否已经在哈希表中如果不在再把 num 和它的下标存进表里继续下一个。def two_sum(nums, target): 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 []为什么要先查后存而不是先存后查这是为了让配对只在历史数据中发生从结构上杜绝同一元素重复使用。举个例子nums [3, 3]target 6。第一步 i0num3补数 3 不在表里存 3→0第二步 i1num3补数 3 在表里且下标是 0返回 [0, 1]。如果调换顺序先存后查在 i0 时先把 3 存进去再查补数 3查到的是自身下标 0返回 [0,0] 就错了。两遍哈希需要显式判断下标不同一遍哈希因为只查历史数据天然绕开了这个坑。这是它更优美的原因也是面试官最爱追问的细节为什么一遍哈希不用检查下标答案就在先查后存这四个字里。3. 多语言实现与工程细节3.1 Python 实现可读性优先Python 用到的是内置 dict底层实现就是哈希表平均 O(1) 插入和查找。上面那段two_sum已经是最精简的写法几个细节值得单独说。第一个细节是enumerate它同时给出下标和值比手写for i in range(len(nums))再nums[i]清晰得多。第二个细节是complement in hash_map这个判断在 dict 上是 O(1) 平均复杂度不用担心性能。第三个细节是返回[hash_map[complement], i]顺序无所谓但逻辑要理清楚一个元素来自历史表一个来自当前遍历。我本地测试时习惯写一个简单的对比脚本用长度为 10 万、随机生成的数组分别跑暴力版和哈希版。实测下来暴力版会明显卡顿哈希版在毫秒级内完成。这种可视化对比会让你对 O(n²) 与 O(n) 的差距产生身体记忆比背十遍复杂度定义都管用。补充一句Python dict 的键要求可哈希这道题的键是整数天然满足。如果你以后处理自定义对象做键记得实现__hash__和__eq__否则会碰到类型错误这是 Python 哈希表最容易踩的暗坑之一。3.2 C 实现性能与陷阱C 里默认用 unordered_map 就够了它才是哈希表如果误用了 map那其实是红黑树查找复杂度是 O(log n)虽然能过题但已经偏离了 O(1) 的初衷。class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash_map; for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (hash_map.find(complement) ! hash_map.end()) { return {hash_map[complement], i}; } hash_map[nums[i]] i; } return {}; } };C 有几个容易翻车的点。第一nums.size()返回的是size_t无符号类型如果拿它和一个负数比较会发生符号转换导致逻辑错乱。稳妥做法是先用int n nums.size()存下来再写循环。第二unordered_map的operator[]在键不存在时会自动插入一个默认值所以判断存在性最好用find()或count()不要用hash_map[complement]作为判断依据否则会产生无效插入拖慢性能。第三返回{}表示空 vector比写临时变量干净。还有一个面试加分项是数值溢出。题目给的数值在 int 范围内target - nums[i]不会溢出但如果面试官把取值范围放大你可以在实现里把complement声明为long long并主动说明这是为了防止极端输入下溢出。这种细节很能体现工程素养。3.3 Java 实现面试常用写法Java 版本的思路和 C 高度相似用 HashMap 即可。class Solution { public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; } map.put(nums[i], i); } return new int[0]; } }Java 的containsKey和get都是 O(1) 平均时间。这里有一个初学者常见错误把泛型写成Mapint, int这是语法错误泛型必须使用包装类型Integer。还有一个细节是返回空数组时习惯写return new int[0]如果面试中希望调用方不处理 null也可以约定返回new int[]{-1, -1}作为哨兵。工程上还会考虑如果输入很大HashMap 的初始容量可以预先设定为nums.length减少扩容带来的 rehash 开销。虽然 LeetCode 的测试集不太需要这种优化但面试时能在代码里主动写出new HashMap(nums.length / 2 * 3)这类预估容量的写法通常会被认为有真实项目经验。3.4 三种解法的复杂度对照与最优性结论把三种思路放在一张表里看结论非常清晰解法时间复杂度空间复杂度适用场景暴力枚举O(n²)O(1)数据量极小或无额外内存可用两遍哈希O(n)O(n)思路清晰适合教学理解一遍哈希O(n)O(n)面试推荐代码简洁且结构严谨为什么说一遍哈希是此题最优解因为它的时间已经压到线性下界——读一遍数组至少是 O(n)不可能比 O(n) 更快空间 O(n) 是换取这个速度的必要代价。如果面试官问能否做到空间 O(1)答案是在无序数组、要求返回下标这两个约束下做不到除非题目改成有序数组或者只问是否存在。能说出这几句约束分析比单纯背结论要有说服力得多。4. 边界情况与测试用例设计4.1 重复元素与索引陷阱这道题最典型的坑是重复元素。举例nums [3, 3]target 6答案只能是 [0, 1]两个下标指向两个不同的 3。一遍哈希没问题但如果你先存后查或者在两遍哈希里忘了下标判断就会出错。我建议把重复元素用例写进自测清单每次提交前过一遍[3, 3], target 6期望 [0, 1][2, 2, 2], target 4期望任意两个不同下标[1, 2, 3], target 6期望空结果虽然题目保证有解代码仍要够健壮第二个用例有个隐蔽点哈希表里键 2 最终只保留一个下标通常是被覆盖后的那个。题目保证唯一解所以无论覆盖与否只要返回的是两个不同下标且值相加等于 target答案都合法。你可能会在不同实现里得到不同组合但都是正确解。不要把这种不确定当成 bug理解背后的覆盖规则才是重点。4.2 负数、零与大数组很多初学者默认数组里全是正数实际上题目说的是整数数组负数完全合法。比如 nums [-3, 4, 3, 90]target 0答案是 [0, 2]因为 -3 3 0。补数计算依然是 target - num结果为负也很正常哈希表键本身支持负数不需要任何额外处理。大数组场景主要考验空间占用。哈希表存 n 个键值对每个键值对在 Python 中大约占 64-72 字节一个长度 100 万的数组哈希表可能要占用 70MB 左右内存。如果面试官追问内存不够怎么办有两个出路一是排序后用双指针空间降到 O(1)但时间升到 O(n log n)二是分块处理或改用数据库索引工程上更复杂。这类讨论能体现出你对时间和空间权衡的敏感度是面试的加分环节。4.3 测试用例设计自查清单我会把这道题的自测整理成一张小表提交代码前手动过一遍用例target期望输出考察点[2, 7, 11, 15]9[0, 1]标准情况[3, 2, 4]6[1, 2]答案不是首尾组合[3, 3]6[0, 1]重复元素[-3, 4, 3]0[0, 2]负数与正数配对[0, 4, 3, 0]0[0, 3]两个零配对[1, 2, 3, 4]8无解健壮性检查最后一行在 LeetCode 上不会真实发生因为题目保证有唯一解但把无解情况写进代码并返回空结果是工程习惯也是面试中的加分细节。我的习惯是先把这些用例写在注释里再动手实现能有效避免写完代码就忘了边界条件的问题。尤其是两个零配对这个用例看起来简单却能快速验证你的索引检查写得对不对。5. 常见问题与排查技巧实录5.1 先存后查为什么错面试里高频追问是一遍哈希里先存后查行不行。从表面看如果数组里有两个相同值且刚好配对先存后查也能返回正确答案但真正的 bug 会出现在结构层面当你把当前元素先存进哈希表再去查询补数时查询结果可能包含当前元素自身。虽然空表起步时不会立刻撞出问题可一旦你在遍历前预置了数据或者数组里出现当前元素恰好等于自己的补数的场景错误就会冒出来。更合理的解释是一遍哈希的历史数据设计表里存的永远是已经遍历过的元素当前元素尚未入表所以配对必然发生在两个不同的下标之间。这个性质是结构自带的不需要额外加判断条件。我在代码 review 时经常看到有人为了保险又加了一个if i ! hash_map[complement]其实一遍哈希下这行判断是多余的画蛇添足还会降低代码可读性。5.2 大数据量下的性能实测我拿长度为 10 万的随机数组做对比跑了 100 次实验暴力解平均耗时到几十秒量级哈希解平均不到 0.02 秒差距超过上千倍。这个结果不是玄学而是线性增长和指数增长的必然差距。LeetCode 上暴力版也能过是因为测试集被压到了时间窗口内但真实系统里 10 万级别数据非常常见O(n²) 直接不可用。性能判断的通用方法是先算上界n10 万时n²/2 是 50 亿次操作现代 CPU 每秒大致能执行 10^9 次简单循环迭代所以至少需要几秒实测几十秒也很正常。哈希版只需 10 万次插入和查询自然在毫秒级。这类数量级直觉我建议每个刷题的人都要刻意训练以后遇到任何问题都能先估算可行性而不是等系统卡死了再回头优化。5.3 面试追问与变形题两数之和的变形题在面试中出现频率极高我整理几个最典型的两数之和 II输入有序数组可以用双指针左右夹逼时间 O(n)、空间 O(1)比哈希表更优。三数之和排序 外层循环 双指针难点在于去重。四数之和乃至任意 k 数之和递归 双指针框架可以通用。两数之和 III设计类要求实现 add 和 find 两个方法本质是设计支持动态增删的哈希表结构。返回所有不重复的组合这时不只返回下标还要考虑值去重通常用排序 双指针解决。我在一次真实面试里经历过的追问路径是先手写一遍哈希版 → 面试官问如果数组有序呢 → 我答双指针 → 又问如果数字频繁增删呢 → 我答设计类哈希表。一套追问下来一题顶三题面试官在十几分钟内就能摸清你对基础数据结构理解的深度。所以我一直不建议只背代码而要把每个解法背后的为什么想透。两数之和刷明白三数之和的框架你就已经会了一半。这道题之所以是热门 100 题的第一题正是因为它把哈希表和双指针两大基础能力浓缩在了一起是真正值得反复咀嚼的母题。最后说个我自己的私人习惯。两数之和是我刷 LeetCode 时写的第一题也是后来带新人时让人家写的第一题。我发现能把这题讲明白的人数据结构基础基本都过关讲不明白的后面刷到 100 题还是容易越刷越虚。所以我一直建议别急着追求秒杀花一个晚上把暴力解、两遍哈希、一遍哈希、有序时的双指针四种思路手写一遍再把边界用例过一遍比连刷十道简单题都值。这题的珍贵不在难而在它把查字典的思维方式浓缩得刚刚好。再送一个小技巧刷完它立刻去翻三数之和的题解你会发现自己已经掌握了双指针版本的两数之和三数之和的内层不过就是它。这种一题牵出多题的刷法比漫无目的地堆题数有效得多。希望这点经验能让你少踩几个我看过的坑。