先交代一下我为什么会写这篇文章。这些年我经常参与算法面试也带过不少新人。面试候选人时我几乎每次都会问两数之和因为这道题几乎所有刷过题的人都会碰见。但有意思的是真把它当回事的人并不多——大多数人都只是背了一版哈希解把答案默写出来然后就进入了下一题。一旦我追问一句为什么哈希表查找是 O(1)或者如果数组特别大内存装不下哈希表你还能怎么解很多人的思路就卡住了。所以我想花一整篇的篇幅把两数之和这道题从题目到解法再到工程应用完整拆一遍。这篇文章不仅适合刚开始刷算法题的同学也适合需要给团队做算法内部分享、或者正被算法面试折磨的工程师。我会把暴力枚举、哈希表、排序双指针这三种主流解法讲清楚再把它的变体三数之和、BST版本、数据流版本和真实项目里的对应场景都展开最后把我踩过的坑一次说完。1. 这道题为什么被称作算法刷题第一题1.1 题目本身其实只有三句话先把原题原样贴出来给定一个整数数组 nums 和一个整数目标值 target 请你在该数组中找出和为目标值 target 的那两个整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。这几句话信息量其实不小。我面试的时候见过不少人在这些细节上翻车所以一句一句拆开看。第一句定义了输入是两个参数一个数组和一个目标值。第二句是关键——返回的是数组下标不是值本身。我见过有候选人最后返回了[2, 7]而不是[0, 1]等于白写。第三句隐藏了三个约束答案唯一、同一个下标不能使用两次、输出顺序不限。许多解法尤其是后面要讲的哈希表正是建立在这几个约束上才成立的。1.2 它究竟在考察什么只看表面它考的是你写没写过基础循环。但面试官看问题的角度完全不同。第一它考察你如何把一个问题从人能理解翻译成机器能执行。暴力枚举是最直白的翻译但这并不丢人。第二它考察复杂度意识。同样是正确解法O(n²) 和 O(n) 的差距在 n10⁵ 时就意味着 10¹⁰ 次运算和 10⁵ 次运算的区别前者在普通机器上要跑几十秒后者眨眼完成。第三它考察数据结构选择能力。数组查找是 O(n)哈希表查找是 O(1)这种用空间换时间的权衡是整个算法面试最核心的考察点。1.3 为什么这道题总被放在第一题这个位置不是随便给的。它不需要任何前置算法知识一个刚学完循环和数组的人就能动手做但它又能自然引出哈希表这种最常用的数据结构。更重要的是它是从暴力到最优的极佳样本。几乎所有经典算法题都能用这条思路去套先想最笨的办法分析重复计算在哪里找出可以通过某种数据结构优化的部分然后实现更优解法。两数之和把这套流程压缩到了二十行代码里所以我一直觉得这道题是算法思维的压缩包。2. 暴力枚举先写对再写好2.1 双重循环的实现思路最直白的思路是拿出第一个数在剩下的数里找有没有target - 第一个数如果没有再拿出第二个数继续找。这就是暴力枚举也叫穷举。def two_sum(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从i 1开始而不是从 0 开始。这既保证了同一个元素不会被使用两遍也避免了重复配对比如[0, 1]和[1, 0]会被当成两种答案的问题。二是找不到时返回空数组这是很多题目默认的行为不要返回None让调用方去猜。2.2 复杂度算清楚外层循环 n 次内层循环平均 n/2 次总共约 n²/2 次比较时间复杂度就是 O(n²)。整个过程只用了几个临时变量空间复杂度 O(1)。如果数组长度只有 100这个复杂度完全无所谓但长度到了 100 万内层循环就可能要执行约 5×10¹¹ 次这在真实机器上是不可接受的。这也是算法复杂度的意义所在很多时候不是不能解而是解不完。2.3 为什么面试时先提暴力解不是减分项我第一次参加算法面试时紧张到直接写哈希解结果被追问得一愣一愣的。后来一位面试官朋友告诉我他其实更希望候选人先分析暴力解再过渡到优化解因为这才是真实工程里的思考路径——先确保功能正确再考虑性能。上来就写最优解反而让他怀疑是不是背题。所以更稳妥的面试节奏是先口头说一句最朴素的做法是双重循环复杂度 O(n²)确认思路正确后再深挖优化。把暴力分析清楚还能帮你验证对题目的理解没有偏差。2.4 暴力解在真实场景里并非一无是处说句公道话O(n²) 不是永远都不可用。如果数组只有几十个元素双重循环的代码比哈希表简单得多也没有哈希冲突、内存占用等问题。在某些嵌入式环境、内存极其受限的场景里O(1) 空间的解法反而比 O(n) 空间的解法更合适。算法题里的最优解到真实项目里未必是最优这一点等讲到工程落点的时候还会再展开。3. 哈希表一次遍历面试官真正想要的那个答案3.1 优化思路到底从哪冒出来的重新审视暴力解法的内层循环它本质上在做一件事在数组里查找target - nums[i]是否存在。既然每次都要查找那我们自然想到能不能提前把所有元素放到一个可以 O(1) 查找的结构里这个结构就是哈希表。思路非常朴素遍历数组对于每一个nums[i]只关心一个问题——在已经见过的元素里有没有target - nums[i]。用一个实际例子走一遍。nums [2, 7, 11, 15]target 9i0nums[0]2需要找 7。此时哈希表为空没找到把2存进去键是 2值是下标 0。i1nums[1]7需要找 2。此时哈希表里有 2命中返回下标[0, 1]。整个过程只遍历一次数组。每个元素进来时先查补数存不存在不存在就把自己存进去等后面的元素来查。这就是一次遍历的精髓。3.2 先查后存 vs 先存后查一个容易写错的细节这里有个细节必须强调必须先查再存。如果先把自己存进去再查就会出问题。数组[3, 3]target6。如果先把nums[0]3存进去再查target - nums[1] 3会发现哈希表里已经有一个 3 了。此时哈希表里的下标是 0而当前下标是 1结果返回[0, 1]看起来没问题。但换个情况数组只有[3]一个元素target6。先存后查时自己会被查到自己错误返回[0, 0]。这就是题目里同一个元素不能使用两遍想要规避的情况。一次遍历的解法因为每个元素都是先查后存当前元素还在外面不可能找到自己天然规避了这个 bug。这是一个很隐蔽的细节面试时主动说出来非常加分。3.3 两种哈希表写法放在一起对比两次遍历版本逻辑更直观但需要额外判断def two_sum_two_pass(nums, target): hashmap {} for i, num in enumerate(nums): hashmap[num] i for i, num in enumerate(nums): complement target - num if complement in hashmap and hashmap[complement] ! i: return [i, hashmap[complement]] return []一次遍历版本也是我最推荐的写法def two_sum_one_pass(nums, target): hashmap {} for i, num in enumerate(nums): complement target - num if complement in hashmap: return [hashmap[complement], i] hashmap[num] i return []两次遍历好理解但多建了整张表多了一轮循环还要专门判断hashmap[complement] ! i。一次遍历在时间、空间上都更优而且代码更简洁。面试时建议直接上一边遍历版本但前提是你能把先查后存的道理说清楚。3.4 哈希表查找为什么是 O(1)用查字典来理解很多人背下了哈希表查找 O(1)但要讲清原理就卡壳。我用一个类比来解释。想象一本按拼音排序的字典。如果想找猫拼音排序可以二分查找每次砍一半复杂度 O(log n)。但如果你在字典侧面做一个索引每个首字母对应一个页码范围那查猫只需要先翻到m这一页再在那一小块里找。哈希表就是这个索引的极致版——通过哈希函数直接把 key 映射到存储位置不需要逐个比较所以大多数情况只需要一次计算加一次内存访问。这就是期望 O(1)的含义。严格来说哈希表最坏情况会退化成 O(n)。如果哈希函数设计得不好或者数据恰好全部碰撞所有 key 都落在同一个桶里查找就又变成线性扫描。在算法题里我们默认哈希表是 O(1)真实工程里选择哈希函数、处理哈希冲突从来都不是纯理论问题。提示面试时被追问哈希冲突怎么办时可以从链地址法、开放寻址法、扩容重哈希这几个方向回答不要只说不知道反正题目能过。3.5 Java 和 C 实现参考只给 Python 不太够面试里最常遇到的还是 Java 和 C我也都贴一遍。Javaclass 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]; } }Cclass Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hashmap; for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (hashmap.count(complement)) { return {hashmap[complement], i}; } hashmap[nums[i]] i; } return {}; } };注意 Java 里HashMap存在自动装箱和哈希碰撞的问题但作为算法题标准写法没有问题。如果面试官往工程方向深挖你可以补充一句数据量极大时可以考虑用IntIntHashMap之类的原始类型哈希表减少装箱开销。3.6 复杂度总结时间上每个元素最多做一次哈希查找、一次哈希插入整体 O(n)。空间上最坏情况所有元素都进了哈希表O(n)。这就是典型的空间换时间——用 O(n) 的额外内存把暴力解的 O(n²) 时间降到了 O(n)。4. 排序双指针另一种值得掌握的思路4.1 双指针是在什么前提下成立的哈希表解法最怕的场景有两个一是不能破坏原数组的顺序但可以接受 O(n) 空间二是题目要求返回值而不是下标或者输入数组本身已经有序。这时候双指针就登场了。排序双指针的核心思想是先把数组排好序然后用一左一右两个指针向中间移动。但双指针这个技巧能成立的前提是数组有序。这个前提决定了它的适用范围。LeetCode 167 就是典型例子输入数组已经有序要求找两个数的下标。哈希表照样能做但双指针的空间复杂度只有 O(1)更优。4.2 指针移动的逻辑为什么是对的先看代码再解释为什么指针只能这样移动。def two_sum_sorted(nums, target): left, right 0, len(nums) - 1 while left right: current nums[left] nums[right] if current target: return [left, right] elif current target: left 1 else: right - 1 return []为什么current target时 left 右移因为数组有序nums[left]是较小的那一端nums[right]是较大的那一端。当前和太小说明小的那头还可以更大一点所以 left 往右走。同理current target时需要把大的那头往左收所以 right 左移。为什么这样移动不会漏掉正确答案关键在于每一步都排除一个不可能的区域如果当前和小于 target那么以当前 left 为左边界的所有组合都不可能凑出 target——因为 right 已经是最大可选值了left 不动时和只会越来越小。所以可以把 left 整个排除。反过来同理。这个排除不可能区域的想法是双指针一类题目共通的正确性证明思路。4.3 时间空间复杂度排序用高效的排序算法平均 O(n log n)。双指针阶段每个元素最多被指针扫到一次是 O(n)。整体 O(n log n)。空间上如果不考虑排序过程本身使用的临时空间双指针阶段是 O(1)比哈希表的 O(n) 有明显优势。4.4 三种解法到底怎么选我用一张表把三种解法放在一起对比解法时间复杂度空间复杂度能否返回原始下标适用场景暴力枚举O(n²)O(1)能n 很小、代码最简单哈希表一次遍历O(n)O(n)能数组无序必须保下标排序双指针O(n log n)O(1)不能除非额外记录数组有序、或只要求返回组合注意最后一行排序会打乱原始下标。如果题目要求返回原始数组下标就不能单纯排序双指针除非你在排序前额外保存一份值-原始下标的映射或者用结构体同时保存值和原始下标。这也是很多人在 LeetCode 167 上卡住的原因——167 恰恰给的是一个已经排好序的数组所以这个问题不存在。5. 两数之和的变体地图从三数之和到数据流5.1 变体一求所有不重复的配对原题只要求返回一组答案但实际场景里经常需要找出所有和等于 target 的不重复组合。哈希表在去重这个问题上很麻烦容易写错。更稳妥的做法是排序双指针配合跳过重复元素。以下代码框架可以直接背下来也是后面三数之和的基础def two_sum_all_pairs(nums, target): nums.sort() res [] left, right 0, len(nums) - 1 while left right: s nums[left] nums[right] if s target: res.append([nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif s target: left 1 else: right - 1 return res那两个跳过重复元素的 while 循环是精髓命中目标后如果左右两侧存在相同值直接移动会得到完全一样的组合必须一次性跳过去。5.2 变体二三数之和三数之和是两数之和最经典的扩展面试频率比两数之和本身还高。核心思路是先排序再固定一个数剩下的两个数用双指针找。也就是把三数之和降级为两数之和。def three_sum(nums, target): nums.sort() n len(nums) res [] for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: current nums[i] nums[left] nums[right] if current target: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif current target: left 1 else: right - 1 return res去重逻辑有三层外层固定值跳过重复内层命中后左右指针各自跳过重复。理解了双指针的移动逻辑之后三数之和完全不需要死记硬背。5.3 变体三二叉搜索树中的两数之和如果输入不是数组而是一棵二叉搜索树怎么做BST 有一个天然性质中序遍历结果是递增序列。所以最直接的思路是先中序遍历把树转成有序数组然后套双指针。这就是把一道树形题降级成数组题。面试时先给出中序遍历双指针的方案一般就足够了。如果继续深挖可以提用两个迭代器从树的两侧向内遍历不额外开数组但这个实现复杂度会高不少需要深刻理解 BST 前驱和后继的概念。5.4 变体四数据流场景真正的数据往往不是一次性给出的数组而是持续到达的流。每来一个新数都需要判断之前是否出现过某个数和它加起来等于 target。这个场景其实就是哈希表一遍遍历的流式版本每来一个新数先查补数在不在集合里再把新数插进去。真实工程里这种模式非常常见。比如接口防重每来一个请求先查请求签名是否在缓存里不在就写入并放行。可以说两数之和的哈希解法本质上就是在教你一个先查后存的流处理套路这也是它被称作经典的原因之一。6. 从刷题到工程两数之和思想在真实项目里的落点6.1 缓存设计里的先查后存真实项目里最常见的哈希表应用就是缓存。读缓存时先查 key 是否存在命中则返回不命中则查数据库并回填。这个流程和两数之和的一遍遍历完全一样先查补数查不到再存自己。顺序一旦错乱就会出大问题——如果先写入缓存再查询并发场景下可能读到刚写入但还没完全初始化的脏数据。6.2 幂等与去重系统在支付、订单这类系统里幂等是刚需同一笔订单号不能重复处理。常规实现就是把已处理的订单号放进哈希集合每次新请求先查是否存在存在就拒绝不存在就写入并处理。这和两数之和里查找补数的思维同源。而且一旦数据量达到千万级、上亿级这个内存哈希集合自然会演进成 Redis、BloomFilter 等分布式方案但底层的先查后存思想没有变。很多人在学了布隆过滤器之后才回头发现原来它和两数之和的哈希表是一脉相通的。6.3 请求合并与参数配对还有一种工程场景判断两个参数组合是否已经存在。比如表中 (A, B) 这个组合是否唯一或者一个批处理任务中 (A, B) 是否重复提交。最常规的做法就是把 A 和 B 拼成一个 key放进哈希集合。这实际上就是两数之和的键值设计思路把两个数的组合映射成一个可比较的 key然后查表、存表。6.4 从算法到架构的变量数据量算法题里 n 通常只有 10⁴ 到 10⁵ 量级哈希表 O(n) 空间无所谓。但真实系统的数据量可能是 10⁹。这时O(n) 空间不再是可忽略的成本。如果内存装不下就要考虑位图、布隆过滤器、外排序、归并等替代方案。我自己做数据去重时几百万数据用哈希集合没问题但到千万级以上就开始评估布隆过滤器和数据库索引了。算法题的价值不在于照搬而在于给你一个基础模型让你能基于这个模型做工程取舍。7. 我在面试和笔试中踩过的坑一次说清7.1 坑一把下标和值搞混这是最冤枉的失分点。题目要返回下标有人写成了返回值。我建议在写代码之前先把题目要求的输出格式用一句话写出来比如返回两个下标组成的数组。写完代码后再对着这个要求检查一遍 return 语句。这个习惯治好了我一半以上因为低级失误导致的测评不通过。7.2 坑二没处理空数组和单元素数组边界条件是面试里的必考项。如果 nums 是空数组暴力解法的循环天然不进入返回[]即可单元素数组也类似。哈希解同样不受影响。但一定要主动思考这些边界否则写出来的代码遇到极端测试用例可能直接数组越界。7.3 坑三target 为负数或 0 时乱了阵脚两数之和没有规定数组和 target 必须为正数。nums [-3, 4, 3, 90]target 0答案应该是[0, 2]。有些人一看到负数就觉得不对其实解法没有任何变化负数照样进哈希表补数照常计算。所以千万别对输入做无根据的假设尤其在面试手写代码时。7.4 坑四整数溢出的隐患如果nums[i]非常大接近整数上限那么nums[i] nums[j]在 Java 里可能溢出成负数导致明明和等于 target 却比较不出来。更稳妥的写法是避免直接相加改成比较target - nums[i] nums[j]用减法替代加法。这既避免溢出也更容易让面试官看到你在处理边界情况。7.5 坑五哈希表覆盖引发重复元素问题数组里如果有重复元素两次遍历的哈希表法有可能查到自己。比如[3, 3]target6如果哈希表把键 3 的值覆盖成后一个下标 1那么第一次遍历时 complement3查到的下标已经变成 1会和自身下标重复返回[1, 1]这种错误。一遍遍历的先查后存天然不存在这个问题这也是我推荐一边遍历版本的原因之一。7.6 坑六面试时一上来就闷头写最优解这是心态问题。我见过太多候选人题目还没分析就开始敲哈希表万一思路卡住整场面试都乱了。更好的方式是先跟面试官对齐思路我准备先用暴力解分析一下再优化。说完暴力解的复杂度再说这里可以用哈希表把查找从 O(n) 降到 O(1)然后开始写。整个过程显得有章法你自己也不容易紧张。提示如果遇到完全没做过的题也先走一遍暴力解 - 复杂度分析 - 优化方向的流程。这个节奏在面试里比最终解法的完美程度更重要。最后分享一个我自己的习惯。刷完两数之和之后我没有急着进入下一题而是花时间把自己代入面试官的角色试着反问自己几个问题如果数组很大内存装不下怎么办如果要求返回所有组合怎么办如果输入本身有序能不能更省这些问题就是我列出的变体章节的来源。事实证明被这些问题折磨过之后再去面试时遇到原题几乎都能讲出比标准答案更深一层的东西。两数之和看起来简单真正吃透它你等于拿到了通往哈希表、双指针、复杂度分析这三座大山的钥匙。
