这道题有意思的地方在于几乎所有刷过算法题的人都做过两数之和它常年挂在LeetCode第一题的位置是很多人算法之路的起点。但我这几年面试下来发现一个很反常的现象很多候选人能秒写出暴力解法或者背诵出哈希表版本但被追问为什么第一题选这个你的解法在内存上到底发生了什么如果数据大到放不进内存怎么办时一下子就露怯了。说白了两数之和不是让你背答案的它考察的是最底层的三个能力能不能从暴力思路里提炼出重复计算、能不能想到用额外空间换时间、能不能把查表这种抽象思维落到具体的代码上。这篇博文不打算停留在AC通过评测就行的层面我把它当一道完整的工程题来拆从暴力解出发推导到哈希表再延伸到真实面试里的变体和追问最后聊几个我自己刷这题和review别人代码时经常踩的坑。1. 题目背后的考察意图为什么两数之和能当算法第一题1.1 先看题面本身信息量其实很小题目描述非常朴素给定一个整数数组nums和一个目标值target要求在数组中找出和为目标值的两个整数返回它们的下标。假设每种输入只对应一个答案且同一个元素不能使用两次。第一次看到这题的人第一反应通常是这有什么难的然后立刻开始写循环。但如果你真的只把它当成一个找两个数的题就浪费了它的价值。这题之所以被排在LeetCode第1题是因为它用最少的背景知识浓缩了算法题最常见的思考链条先有暴力解再看瓶颈最后引入数据结构优化。我见过不少培训机构的课件把这道题归类为哈希表入门题这没有错但它忽略了一个前提你首先得能意识到暴力解的问题在哪。没有这一步你用哈希表只是记住了答案而不是推导出答案。1.2 从能过到会做一题三解的递进关系很多选择题解的朋友会困惑既然哈希表O(n)能过为什么还要看暴力解我举一个自己带新人时常用的比喻暴力解相当于你在一堆书里找某一本一本一本地翻哈希表相当于你先把每本书的位置记在一个小本子上再查位置。后者快但你多花了一个本子空间。这个本子到底值不值取决于书的数量。10本书的时候一本本翻很快10万本书的时候小本子的优势就体现出来了。算法题的复杂度分析本质上就是在算翻书和记本子哪个划算。所以这道题的正确学习路径是先老老实实分析暴力解为什么是O(n²)再体验哈希表如何把查找从O(n)降到O(1)这样才能真正理解空间换时间不是一句空话。2. 暴力解法不是不能写但你要清楚代价是什么2.1 两层循环的复杂度推导暴力解法的代码极其简单以Python为例def two_sum_brute_force(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 []关键在于第二层循环为什么从i 1开始题目要求同一个元素不能使用两次所以j不能等于i同时为了避免重复配对前一个循环已经处理过的组合不需要再检查所以从i 1开始。这是第一个容易忽略的细节很多人写成了for j in range(n)虽然也能通过但平白多算了一倍的无效组合。时间复杂度是经典的等差数列求和当i 0时内层跑n-1次i 1时跑n-2次累计约n(n-1)/2次比较。去掉常数项和低阶项就是 O(n²)。空间复杂度是 O(1)因为只用了两个下标变量。2.2 O(n²)在真实场景中意味着什么如果你只在LeetCode的测试用例里跑n通常是几百到几千O(n²)也能秒出结果。但放到真实业务里情况完全不同。我举个实际发生过的例子曾经有同事写了一段匹配逻辑输入是一份十几万行的用户名单两层循环去查重复项。本机测试用小样本没问题上线后发现接口响应时间从50ms涨到了8秒数据库连接池被打满。原因就是数据量上了十万级以后O(n²)的曲线变得非常陡峭。从数学上说n从1000涨到10000O(n²)的耗时理论上会涨约100倍而O(n)只会涨约10倍。这道算法题想教你的第一课就是这个差距。所以刷题时不要只满足于用暴力解AC了要养成一个习惯看一眼数据规模如果n可以到10^5以上O(n²)基本就该被淘汰了。提示LeetCode上这道题的nums长度可以到10^4甚至10^5级别暴力解在极限数据下可能会超时。这也是为什么官方题解直接给哈希表方案的底层原因。3. 哈希表解法为什么一次遍历就够以及里面的几个陷阱3.1 核心思想是反向查表暴力解慢在哪儿慢在对于每一个nums[i]都要线性扫描一遍后面所有元素去确认是否存在某个数等于target - nums[i]。换句话说查找补数这一操作是O(n)的。哈希表方案的核心思路非常直接把找补数变成查补数。第一次遍历时我们可以把已经见过的数值存到一个HashMap里key是数值本身value是下标。等遍历到后面的元素时只需要判断target - nums[i]是否在HashMap里就能O(1)找到答案。为什么HashMap的查找是O(1)这里需要啰嗦一句底层原理因为它关系到你能不能把这个方案迁移到别的题目上。HashMap内部是一个数组 链表或红黑树通过哈希函数把key映射到数组索引理想情况下直接一步定位。哈希冲突时退化为链表查询但设计良好的哈希函数和负载因子控制下平均还是O(1)。3.2 一次遍历与两次遍历的差别哈希表解法有两种写法。第一种是两次遍历的版本def two_sum_two_pass(nums, target): hash_map {} for idx, value in enumerate(nums): hash_map[value] idx for idx, value in enumerate(nums): complement target - value if complement in hash_map and hash_map[complement] ! idx: return [idx, hash_map[complement]] return []第二种是真正推荐的一次遍历版本def two_sum_one_pass(nums, target): hash_map {} for idx, value in enumerate(nums): complement target - value if complement in hash_map: return [hash_map[complement], idx] hash_map[value] idx return []一次遍历的逻辑是边遍历边建表先查当前元素的补数是否已经出现过如果出现过直接返回否则把当前元素放入表里。很多初学者会问这个顺序不会漏掉补数在后面的情况吗不会。因为当你遍历到后面那个元素时前面那个元素已经被放进哈希表了届时依然能查到。两次遍历的版本需要额外处理一个细节hash_map[complement] ! idx。因为如果补数和当前值是同一个元素会造成自己加自己等于target的误判。比如nums [3]target 6如果没有这个判断两次遍历会返回[0, 0]违反了同一个元素不能使用两次的约束。3.3 重复元素问题的处理还有一个经常踩的坑当数组里有重复值时HashMap的value到底存哪个下标比如nums [3, 2, 4]target 6答案是[1, 2]。这个用例没问题。但如果数组是nums [3, 3]target 6下标是0和1。两次遍历的写法里hash_map[value] idx会把前面那个3的下标0覆盖成1导致查不到答案。这就是为什么我强烈推荐一次遍历版本。在两次遍历版本里你需要自己绕开这个坑比如存所有下标的列表或判断下标是否相同但一次遍历从结构上就规避了它因为每个元素只在被遍历到时才放入HashMap和自己补数配对时补数一定是之前遍历过的元素下标不会重复。注意HashMap的key是元素值value是下标。重复值会产生key冲突此时value会覆盖为最新下标。在只要求返回一组答案的题设下后一个下标往往更有用但一定要理解覆盖行为而不是死记代码。4. 题目变体与面试追问从背答案到有思路4.1 数组有序时用双指针把空间省成O(1)如果面试官加一个条件数组已经排好序你的解法就必须跟着变。这时候哈希表依然能解但空间复杂度O(n)就没有必要了——有序数组最好的解法是双指针。双指针的思路是左指针指向开头右指针指向结尾计算两数之和。如果和大于target说明需要减小右指针左移如果和小于target说明需要增大左指针右移。代码实现def two_sum_sorted(nums, target): left, right 0, len(nums) - 1 while left right: current_sum nums[left] nums[right] if current_sum target: return [left, right] elif current_sum target: left 1 else: right - 1 return []这个解法背后是一个很实用的单调性观察左指针右移会增大和右指针左移会减小和。每次移动都能排除一部分不可能的组合整体复杂度O(n)。这种利用有序性收缩搜索空间的思路在三数之和最接近的三数之和等题目里会再次出现值得重点消化。4.2 返回所有不重复组合哈希表的困境还有一个高频变体不要求返回下标要求返回所有不重复的数字组合。比如nums [1, 2, 3, 2]target 4正确答案是[[1, 3]][2, 2]虽然数值上等价但需要去重。这种题用哈希表会稍微有些别扭因为去重需要额外记录已经输出过的组合。更干净的做法是排序 双指针配合跳过重复元素的逻辑这也是三数之和的标准解法思路。我把两种方案的适用场景列个表题目要求推荐方案时间复杂度空间复杂度返回一组下标无需关心顺序哈希表一次遍历O(n)O(n)数组有序追求最低空间双指针O(n)O(1)返回所有不重复组合排序 双指针O(n log n)O(1)排序栈空间除外4.3 数据量巨大哈希表也不是银弹上面的讨论都假设数据能完整放进内存。但如果面试官继续追问数组太大了哈希表放不下怎么办你就需要给出分治思路了。最常见的回答框架是外排序 双指针先把数组分块排序存到磁盘上然后在外部归并的过程中用双指针查找。或者用分布式思路把数组分到多台机器上每台机器算局部哈希表再汇总结果。这类问题的考察点不在SQL或者具体框架而是你有没有数据规模会改变算法选择的意识。哈希表再好用数据量大到内存放不下依然要回到磁盘I/O和分布式的范畴。我在面试中比较欣赏的回答是如果单机内存有限我会先用外部排序把数据有序化再用双指针扫描这样空间占用是常数级别如果数据分布在多台机器上我会用分布式哈希表或者MapReduce框架。这句话虽然不写代码但体现的工程判断比默写HashMap更重要。5. 我刷这道题时踩过的坑以及复盘建议5.1 最常见的三个错误第一个错误是边界条件处理不当。比如没有判断complement in hash_map时是否下标相同导致nums [3]target 6时错误返回[0, 0]。第二个错误是忽略了重复值的覆盖问题上面提到过不再赘述。第三个错误比较隐蔽有人会在一次遍历版本里先hash_map[nums[i]] i再查找补数导致当前元素自己被当成补数。用代码演示第三个错误# 错误写法 for idx, value in enumerate(nums): hash_map[value] idx complement target - value if complement in hash_map: return [hash_map[complement], idx]当value * 2 target时这个写法会直接返回[idx, idx]。比如nums [3, 1]target 6它会在处理第一个元素时返回[0, 0]因为hash_map[3]就是刚放进去的自己。正确顺序必须是先查补数再放当前元素。5.2 我建议的练习路径如果你刚入门我建议不要把这道题刷一遍就完事。我在带新人时给的路径是先用暴力解AC再分析为什么慢然后手写一次遍历哈希表故意写成上面三种错误版本观察为什么报错或者结果不对最后尝试在纸上分析如果数组有序双指针方案应该怎么写。等这些都做完可以顺手把三数之和和最接近的三数之和也刷了。你会发现两个数的双指针思路一旦掌握三个数只是在外层多套一层循环而已。这道题最大的价值不在于它本身而在于它是你理解暴力 → 查表优化 → 利用有序性收缩空间整条思考链的入口。我自己复习算法时有个习惯每道题刷完会在题解末尾写一句话总结这题到底考了什么能力模型。两数之和我写的是查找问题本质上是数据组织方式的问题HashMap把查找变成O(1)但你要为它付空间成本。这句话比任何代码都更能帮我在一个月后回忆起这道题的核心。 
长河君 · 2026/10/9 8:13:59 · 阅读 1.2k 两数之和：从暴力解到哈希表，算法第一题背后的工程思维
这道题有意思的地方在于几乎所有刷过算法题的人都做过两数之和它常年挂在LeetCode第一题的位置是很多人算法之路的起点。但我这几年面试下来发现一个很反常的现象很多候选人能秒写出暴力解法或者背诵出哈希表版本但被追问为什么第一题选这个你的解法在内存上到底发生了什么如果数据大到放不进内存怎么办时一下子就露怯了。说白了两数之和不是让你背答案的它考察的是最底层的三个能力能不能从暴力思路里提炼出重复计算、能不能想到用额外空间换时间、能不能把查表这种抽象思维落到具体的代码上。这篇博文不打算停留在AC通过评测就行的层面我把它当一道完整的工程题来拆从暴力解出发推导到哈希表再延伸到真实面试里的变体和追问最后聊几个我自己刷这题和review别人代码时经常踩的坑。1. 题目背后的考察意图为什么两数之和能当算法第一题1.1 先看题面本身信息量其实很小题目描述非常朴素给定一个整数数组nums和一个目标值target要求在数组中找出和为目标值的两个整数返回它们的下标。假设每种输入只对应一个答案且同一个元素不能使用两次。第一次看到这题的人第一反应通常是这有什么难的然后立刻开始写循环。但如果你真的只把它当成一个找两个数的题就浪费了它的价值。这题之所以被排在LeetCode第1题是因为它用最少的背景知识浓缩了算法题最常见的思考链条先有暴力解再看瓶颈最后引入数据结构优化。我见过不少培训机构的课件把这道题归类为哈希表入门题这没有错但它忽略了一个前提你首先得能意识到暴力解的问题在哪。没有这一步你用哈希表只是记住了答案而不是推导出答案。1.2 从能过到会做一题三解的递进关系很多选择题解的朋友会困惑既然哈希表O(n)能过为什么还要看暴力解我举一个自己带新人时常用的比喻暴力解相当于你在一堆书里找某一本一本一本地翻哈希表相当于你先把每本书的位置记在一个小本子上再查位置。后者快但你多花了一个本子空间。这个本子到底值不值取决于书的数量。10本书的时候一本本翻很快10万本书的时候小本子的优势就体现出来了。算法题的复杂度分析本质上就是在算翻书和记本子哪个划算。所以这道题的正确学习路径是先老老实实分析暴力解为什么是O(n²)再体验哈希表如何把查找从O(n)降到O(1)这样才能真正理解空间换时间不是一句空话。2. 暴力解法不是不能写但你要清楚代价是什么2.1 两层循环的复杂度推导暴力解法的代码极其简单以Python为例def two_sum_brute_force(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 []关键在于第二层循环为什么从i 1开始题目要求同一个元素不能使用两次所以j不能等于i同时为了避免重复配对前一个循环已经处理过的组合不需要再检查所以从i 1开始。这是第一个容易忽略的细节很多人写成了for j in range(n)虽然也能通过但平白多算了一倍的无效组合。时间复杂度是经典的等差数列求和当i 0时内层跑n-1次i 1时跑n-2次累计约n(n-1)/2次比较。去掉常数项和低阶项就是 O(n²)。空间复杂度是 O(1)因为只用了两个下标变量。2.2 O(n²)在真实场景中意味着什么如果你只在LeetCode的测试用例里跑n通常是几百到几千O(n²)也能秒出结果。但放到真实业务里情况完全不同。我举个实际发生过的例子曾经有同事写了一段匹配逻辑输入是一份十几万行的用户名单两层循环去查重复项。本机测试用小样本没问题上线后发现接口响应时间从50ms涨到了8秒数据库连接池被打满。原因就是数据量上了十万级以后O(n²)的曲线变得非常陡峭。从数学上说n从1000涨到10000O(n²)的耗时理论上会涨约100倍而O(n)只会涨约10倍。这道算法题想教你的第一课就是这个差距。所以刷题时不要只满足于用暴力解AC了要养成一个习惯看一眼数据规模如果n可以到10^5以上O(n²)基本就该被淘汰了。提示LeetCode上这道题的nums长度可以到10^4甚至10^5级别暴力解在极限数据下可能会超时。这也是为什么官方题解直接给哈希表方案的底层原因。3. 哈希表解法为什么一次遍历就够以及里面的几个陷阱3.1 核心思想是反向查表暴力解慢在哪儿慢在对于每一个nums[i]都要线性扫描一遍后面所有元素去确认是否存在某个数等于target - nums[i]。换句话说查找补数这一操作是O(n)的。哈希表方案的核心思路非常直接把找补数变成查补数。第一次遍历时我们可以把已经见过的数值存到一个HashMap里key是数值本身value是下标。等遍历到后面的元素时只需要判断target - nums[i]是否在HashMap里就能O(1)找到答案。为什么HashMap的查找是O(1)这里需要啰嗦一句底层原理因为它关系到你能不能把这个方案迁移到别的题目上。HashMap内部是一个数组 链表或红黑树通过哈希函数把key映射到数组索引理想情况下直接一步定位。哈希冲突时退化为链表查询但设计良好的哈希函数和负载因子控制下平均还是O(1)。3.2 一次遍历与两次遍历的差别哈希表解法有两种写法。第一种是两次遍历的版本def two_sum_two_pass(nums, target): hash_map {} for idx, value in enumerate(nums): hash_map[value] idx for idx, value in enumerate(nums): complement target - value if complement in hash_map and hash_map[complement] ! idx: return [idx, hash_map[complement]] return []第二种是真正推荐的一次遍历版本def two_sum_one_pass(nums, target): hash_map {} for idx, value in enumerate(nums): complement target - value if complement in hash_map: return [hash_map[complement], idx] hash_map[value] idx return []一次遍历的逻辑是边遍历边建表先查当前元素的补数是否已经出现过如果出现过直接返回否则把当前元素放入表里。很多初学者会问这个顺序不会漏掉补数在后面的情况吗不会。因为当你遍历到后面那个元素时前面那个元素已经被放进哈希表了届时依然能查到。两次遍历的版本需要额外处理一个细节hash_map[complement] ! idx。因为如果补数和当前值是同一个元素会造成自己加自己等于target的误判。比如nums [3]target 6如果没有这个判断两次遍历会返回[0, 0]违反了同一个元素不能使用两次的约束。3.3 重复元素问题的处理还有一个经常踩的坑当数组里有重复值时HashMap的value到底存哪个下标比如nums [3, 2, 4]target 6答案是[1, 2]。这个用例没问题。但如果数组是nums [3, 3]target 6下标是0和1。两次遍历的写法里hash_map[value] idx会把前面那个3的下标0覆盖成1导致查不到答案。这就是为什么我强烈推荐一次遍历版本。在两次遍历版本里你需要自己绕开这个坑比如存所有下标的列表或判断下标是否相同但一次遍历从结构上就规避了它因为每个元素只在被遍历到时才放入HashMap和自己补数配对时补数一定是之前遍历过的元素下标不会重复。注意HashMap的key是元素值value是下标。重复值会产生key冲突此时value会覆盖为最新下标。在只要求返回一组答案的题设下后一个下标往往更有用但一定要理解覆盖行为而不是死记代码。4. 题目变体与面试追问从背答案到有思路4.1 数组有序时用双指针把空间省成O(1)如果面试官加一个条件数组已经排好序你的解法就必须跟着变。这时候哈希表依然能解但空间复杂度O(n)就没有必要了——有序数组最好的解法是双指针。双指针的思路是左指针指向开头右指针指向结尾计算两数之和。如果和大于target说明需要减小右指针左移如果和小于target说明需要增大左指针右移。代码实现def two_sum_sorted(nums, target): left, right 0, len(nums) - 1 while left right: current_sum nums[left] nums[right] if current_sum target: return [left, right] elif current_sum target: left 1 else: right - 1 return []这个解法背后是一个很实用的单调性观察左指针右移会增大和右指针左移会减小和。每次移动都能排除一部分不可能的组合整体复杂度O(n)。这种利用有序性收缩搜索空间的思路在三数之和最接近的三数之和等题目里会再次出现值得重点消化。4.2 返回所有不重复组合哈希表的困境还有一个高频变体不要求返回下标要求返回所有不重复的数字组合。比如nums [1, 2, 3, 2]target 4正确答案是[[1, 3]][2, 2]虽然数值上等价但需要去重。这种题用哈希表会稍微有些别扭因为去重需要额外记录已经输出过的组合。更干净的做法是排序 双指针配合跳过重复元素的逻辑这也是三数之和的标准解法思路。我把两种方案的适用场景列个表题目要求推荐方案时间复杂度空间复杂度返回一组下标无需关心顺序哈希表一次遍历O(n)O(n)数组有序追求最低空间双指针O(n)O(1)返回所有不重复组合排序 双指针O(n log n)O(1)排序栈空间除外4.3 数据量巨大哈希表也不是银弹上面的讨论都假设数据能完整放进内存。但如果面试官继续追问数组太大了哈希表放不下怎么办你就需要给出分治思路了。最常见的回答框架是外排序 双指针先把数组分块排序存到磁盘上然后在外部归并的过程中用双指针查找。或者用分布式思路把数组分到多台机器上每台机器算局部哈希表再汇总结果。这类问题的考察点不在SQL或者具体框架而是你有没有数据规模会改变算法选择的意识。哈希表再好用数据量大到内存放不下依然要回到磁盘I/O和分布式的范畴。我在面试中比较欣赏的回答是如果单机内存有限我会先用外部排序把数据有序化再用双指针扫描这样空间占用是常数级别如果数据分布在多台机器上我会用分布式哈希表或者MapReduce框架。这句话虽然不写代码但体现的工程判断比默写HashMap更重要。5. 我刷这道题时踩过的坑以及复盘建议5.1 最常见的三个错误第一个错误是边界条件处理不当。比如没有判断complement in hash_map时是否下标相同导致nums [3]target 6时错误返回[0, 0]。第二个错误是忽略了重复值的覆盖问题上面提到过不再赘述。第三个错误比较隐蔽有人会在一次遍历版本里先hash_map[nums[i]] i再查找补数导致当前元素自己被当成补数。用代码演示第三个错误# 错误写法 for idx, value in enumerate(nums): hash_map[value] idx complement target - value if complement in hash_map: return [hash_map[complement], idx]当value * 2 target时这个写法会直接返回[idx, idx]。比如nums [3, 1]target 6它会在处理第一个元素时返回[0, 0]因为hash_map[3]就是刚放进去的自己。正确顺序必须是先查补数再放当前元素。5.2 我建议的练习路径如果你刚入门我建议不要把这道题刷一遍就完事。我在带新人时给的路径是先用暴力解AC再分析为什么慢然后手写一次遍历哈希表故意写成上面三种错误版本观察为什么报错或者结果不对最后尝试在纸上分析如果数组有序双指针方案应该怎么写。等这些都做完可以顺手把三数之和和最接近的三数之和也刷了。你会发现两个数的双指针思路一旦掌握三个数只是在外层多套一层循环而已。这道题最大的价值不在于它本身而在于它是你理解暴力 → 查表优化 → 利用有序性收缩空间整条思考链的入口。我自己复习算法时有个习惯每道题刷完会在题解末尾写一句话总结这题到底考了什么能力模型。两数之和我写的是查找问题本质上是数据组织方式的问题HashMap把查找变成O(1)但你要为它付空间成本。这句话比任何代码都更能帮我在一个月后回忆起这道题的核心。