两数之和与哈希表：从暴力解到O(n)最优解

我先说个有意思的现象很多人开始刷算法题的时候第一道题往往不是“两数之和”但第一道卡住的题大概率是它。说它简单吧暴力解一眼就能写出来说它难吧真正能从O(n²)优化到O(n)、把哈希表用明白的人确实不多。我当年就是在这道题上意识到——算法面试考察的其实不是你背了多少模板而是你对“数据怎么组织”这件事有没有直觉。这篇就借着两数之和把哈希表这个方法彻底讲透从暴力解到最优解从原理到代码实现再到重复元素那些容易翻车的细节一步不落。适合刚接触数据结构和算法、准备校招或跳槽刷题的朋友。1. 两数之和到底在考什么题目没那么简单两数之和是LeetCode的第1题题目描述非常简短给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案但是数组中同一个元素不能使用两遍。就这么一句话很多人第一次看到都会觉得太容易了。两层for循环嵌套外层从0开始内层从i1开始逐对检查nums[i] nums[j] target找到就返回下标完事。但恰恰是这个“一眼就会”的暴力解掩盖了这道题真正的考察点。这题要考察的核心能力有三个层面。第一层你能不能看出暴力解的问题在哪嵌套循环的O(n²)时间复杂度在大数据量下有多不可忍受。第二层你能不能想到用空间换时间用一个额外的数据结构哈希表把查找时间从O(n)降到O(1)。第三层也是面试中最常翻车的——你能不能处理好边界条件比如重复元素、目标值等于两倍某个元素的情况。这三层递进正好对应一线程序员从“能写代码”到“写得高效”再到“写得稳”的成长路径。我面试别人的时候经常把这道题当第一道热身题。候选人写暴力解不算错但如果能主动提出“其实可以用哈希表把复杂度降下来”这人的数据结构和算法底子基本就有保障了。反过来如果连哈希表这个名字都没提过后面的问题就得从基础开始问起。所以别小看这道“第1题”。它考的东西非常本质你愿不愿意在动手写代码之前先花30秒想一想数据该用什么结构而不是找到一个可行解就直接交差。这个习惯比这道题本身值钱得多。2. 两种解法的本质区别暴力是找组合哈希是找差值要弄清楚为什么哈希表方案更优先得彻底看懂暴力解法的底牌。2.1 暴力解法的时间开销到底有多大暴力解法的代码很简单def two_sum_brute(nums, target): for i in range(len(nums)): for j in range(i 1, len(nums)): if nums[i] nums[j] target: return [i, j] return []逻辑上它做的事是“枚举所有二元组合”。数组有n个元素所有配对数量是C(n,2)n(n-1)/2所以时间复杂度是O(n²)。当n等于10的时候也就45次比较但当n等于10万的时候需要比较约50亿次。这在真实业务数据量下是没法接受的。更关键的问题在于暴力解法把“查找”这件事给忽略了。你仔细想想内层循环每次都在做同一件事——线性扫描一个数nums[j]去判断它和nums[i]之和是否等于target。每次扫描都是O(n)的遍历但每次的查询目标其实是一样就是“有没有一个数等于target - nums[i]”。这种重复的线性扫描完全可以换一种组织方式来加速。2.2 哈希表把“数组”变成了“字典”哈希表的核心思想是建立一个从“键”到“值”的直接映射。你可以把它理解成一本字典你想查一个字的意思如果字典按拼音排序你按页码一页页翻那就是线性扫描如果字典前面有个索引目录直接告诉你这个字在第几页那就是哈希表做的事。哈希表通过哈希函数把键映射到存储位置理想情况下每次查找只需要O(1)的时间。这也就是说原来暴力解里内层for循环干的活——遍历整个数组找目标值——在哈希表里变成了“一次直接命中”的查询我要找target - nums[i]这个数字存不存在存在的话下标是多少直接问哈希表就能拿到答案。这带来一个思维上的转变暴力解是在找“两个数的组合”哈希表方案是在找“差值”。既然题目要的是两数之和等于target那么对于当前元素x我真正关心的不是另一个数是谁而是target - x在数组里出现过没有。这个问题正好是哈希表最擅长回答的。2.3 “边遍历、边查表、边存表”的单次遍历技巧明白哈希表能快查之后还有一个关键设计不能搞错应当边遍历数组边构建哈希表而不是先把整个数组一次性装进哈希表再开始查。假设你先把数组全部存入哈希表键为值值为下标再遍历查找就会遇到一个经典的bug——比如nums[3, 3]target6。先建表后由于键是3、3重复后写入的覆盖前面的表里只有一个键、值为下标1。再来循环查找时第一个3查到自己的下标1返回[0,1]看似没问题但换个场景nums[3, 2, 3]target6先建表后3的下标被更新为2遍历到第一个3时查到了下标2返回[0, 2]这恰好是对的可是如果遍历到最后一个3查到下标2就会返回[2, 2]这明显不对——同一个元素不能使用两遍。先查后存、边遍历边构建就能从根上避免这个问题因为当前元素还没写入哈希表所以查到的一定是之前已经遍历过的元素的下标绝不会出现“自己匹配自己”的情况。我最早学这个方案的时候就困惑过为什么不是先建表后来在[3,3]这种用例上摔了一跤才明白这个顺序是刻在哈希表方案骨子里的不是为了显得高深是边界安全的需要。3. 哈希表的两个选型问题用什么容器、为什么哈希表是一个抽象概念落到具体代码里不同语言提供的容器不一样。我见过不少人在原理上明白了但一写代码就被容器的选择和API卡住。3.1 Python里的dict直接用最顺手Python里最常用的哈希表实现就是dict。它是用哈希表实现的键值对结构键会自动哈希查找在平均情况下是O(1)的甚至都不用你主动去处理哈希冲突解释器全包了。写起来也非常自然def two_sum_hash(nums, target): record {} for i, num in enumerate(nums): diff target - num if diff in record: return [record[diff], i] record[num] i return []这里if diff in record就是在做哈希查询时间复杂度O(1)。整段代码只有一次for循环所以总复杂度O(n)。对Python刷题来说这是最推荐也是最简洁的版本。3.2 C里别顺手用了mapunordered_map才是哈希表C的初学者很容易踩一个坑以为std::map就是哈希表。其实std::map底层是红黑树插入和查找的复杂度都是O(log n)不是O(1)。真正基于哈希表实现的容器是std::unordered_map。两数之和这种场景我们要的就是O(1)的平均查找所以必须用unordered_map。代码可以这样写#include vector #include unordered_map std::vectorint twoSum(std::vectorint nums, int target) { std::unordered_mapint, int record; for (int i 0; i nums.size(); i) { int diff target - nums[i]; auto it record.find(diff); if (it ! record.end()) { return {it-second, i}; } record[nums[i]] i; } return {}; }这里record.find(diff)就是哈希查找如果找不到find会返回end()。代码里也要注意先查后存和Python版本的逻辑完全一致。如果你在面试现场用的是C一定要说出“用unordered_map而不是map因为红黑树的log n还不如直接排序来得划算”这种级别的细节会很加分。3.3 Java和Go等语言的对应实现Java用户用的是HashMapInteger, Integer用法基本同理MapInteger, Integer record new HashMap(); for (int i 0; i nums.length; i) { int diff target - nums[i]; if (record.containsKey(diff)) { return new int[]{record.get(diff), i}; } record.put(nums[i], i); } return new int[0];Go语言里对应的是map[int]intfunc twoSum(nums []int, target int) []int { record : make(map[int]int) for i, num : range nums { if j, ok : record[target - num]; ok { return []int{j, i} } record[num] i } return nil }所有语言在这个问题上思路完全一致核心就是建一个值到下标的映射然后在遍历过程中查差值。原理搞明白了换语言只是API层面的差异无脑迁移即可。3.4 为什么哈希表方案实际上更快有读者可能会想虽然暴力解是O(n²)但哈希表构建的时候不是也要O(n)时间去插入每个元素吗这不就是两个O(n)吗其实不是插入是哈希表实现里最基本的操作每插入一个键值对平均也是O(1)的。遍历n个元素每个元素做一次O(1)的查询加一次O(1)的插入总共就是O(n)。再算上空间复杂度哈希表开辟了一个最多存n个元素的表所以额外空间是O(n)。这是一种典型的空间换时间。在现在的计算机内存条件下几百万个整数占的空间也就几十兆用这点空间把时间从平方级降到线性级绝大多数场景都是划算的。所以这道题的要求——O(n)时间、O(n)空间——就是面试环节里对两数之和的最优解要求。能在白板上写出这个方案并且能解释清楚为什么不是先建表后遍历这道热身题基本就过了。4. 常见翻车点实录重复元素、负数、以及更多边界情况我再单独拿出一节来讲坑是因为这些坑如果不提前踩一次自己闷头写很容易在错误的方向上浪费大量时间。4.1 重复元素最经典的覆盖问题前面说到先建表后遍历会导致键被覆盖。这其实只是问题的一半。在正确的“边遍历边查”版本里也要留意重复元素的场景——但这时边遍历边查的写法天然防御住了。举个例子nums[1, 6, 3, 3]target6。正确答案应该是[2, 3]因为336两个3的下标分别是2和3。边遍历边查的过程是这样的i0num1差值是5查不到记录1的下标0i1num6差值是0查不到记录6的下标1i2num3差值是3查不到表里还没有3记录3的下标2i3num3差值是3表里能查到3下标是2返回[2, 3]。完美。如果换成先建表后遍历插入3的时候下标2会被下标3覆盖最后表里3的下标变成3遍历到第一个3时查到下标3返回[2, 3]——这次碰巧也是对的。但万一答案是第一个3和第二个3如上面例子先建表后遍历就很容易把同一个元素的下标用两次或者直接覆盖掉正确答案。这种bug非常隐蔽不写测试很难发现。4.2 负数与零的处理两数之和不代表两个数都是正数。比如nums[-3, 4, 3, 90]target0答案是[0, 2]-3 3 0。有些同学看到负数就慌了其实不用。哈希表方案压根不关心数字是正还是负差值的计算target - num照常负数照样可以作为键存进去。哈希表查找时比较的就是两个键是否相等跟正负无关。还有一个边界是target本身可能是0。这意味着两个数可能是0和0也可能是一正一负。上面说到的边查边存的逻辑完全不用改直接套就行。4.3 没有答案的输入题目保证每种输入只有一个答案但实际工程中你不会永远这么幸运。如果遍历完了还没找到返回空数组或者抛出异常要跟面试官确认好约定。工程视角下建议函数返回空容器而不是抛出异常因为调用方很可能把“没找到”当成一种合法状态而不是错误状态。4.4 哈希冲突会拖慢性能吗底层实现上哈希表确实有可能出现哈希冲突——两个不同的键被哈希到同一个桶。处理冲突的办法通常是链地址法拉链法或开放寻址法Python的dict用的是开放寻址法C的unordered_map用的则是链地址法。冲突多了之后最坏情况下某个桶里的元素会变多查找就不再是O(1)了会退化成O(k)k是该桶里的元素个数。但工程实现里的哈希函数都设计得很好键的分布足够随机所以平均的冲突率很低实际表现依然接近O(1)。刷算法题阶段完全不需要自己实现哈希表能用对现成容器就够了。只有在极端的面试深挖环节面试官可能会让你手写一个简易哈希表那就是另一道题了。4.5 一个容易让人混淆的误区两数之和的返回值要不要排序这个问题常被误认为是“返回无序对”还是“有序对”。题目要求返回的是下标数组一般期望先较小的下标、后较大的下标。在边遍历边查的写法里我们查到的it-second一定是更早出现过的元素下标而i是当前元素下标因为i从0开始递增所以it-second天然小于i。这保证了返回结果有序不需要额外排序。如果你改动写法把先查后存改成先存后查这个有序性也有可能被破坏虽然在结果正确性上可能不影响但是和题目的输出要求对不上的时候评测就会报错。5. 从两数之和到更广的哈希表应用它只是个缩影其实我在教别人这道题的时候更推荐把这题当成一个“引子”。因为哈希表在算法面试里的出镜率非常高几乎出现在每一类“找关系”的问题中。5.1 哈希表能解决的一类关系问题两数之和本质上是查找“当前元素的历史配对信息”。这类问题的共同模式是遍历一遍数据过程中不断记录已访问信息同时用O(1)的时间查询历史记录是否满足某种条件。类似的两数之和变体有三数之和不再用哈希表直接解决因为三数之和需要先去重哈希表自己去重很麻烦一般做法是先排序再用双指针时间复杂度O(n²)。这个我在后面细说。四数之和同样先排序再用两层循环加双指针跳跃着去重复杂度O(n³)上限但实际运行时会好很多。两数之和的升级版如果数组是排好序的其实不需要哈希表用双指针一左一右往中间缩就可以O(n)解决连额外空间都省了。这告诉我们要根据输入特征选方案不盲目套哈希表。最长连续序列要求O(n)典型的哈希表场景把每个数字存进set再对每个数字判断它是否是连续序列的开头它的前一个数不在set里然后往右扩展统计长度。字母异位词分组把每个排序后的字符串作为哈希表的键异位词全部塞进对应的值列表最后统一输出。这些题目里都能看到“哈希表作为快速查找索引”的身影。想明白两数之和之后再去看最长连续序列和字母异位词分组会顺畅很多。5.2 两数之和为什么不用双指针双指针又输在哪很多人刷过几道题之后会产生一个思维惯性凡是“找两个数满足某种关系”的问题都先排序再双指针。这思路在“有序数组找和”是没错的但两数之和这道题要求的返回值是原数组的下标。如果先排序下标就全乱了。除非你再单独维护一个配对数组记录值和原下标的对应关系但这就徒增复杂度。相比之下哈希表方案完全不需要动数组的原始顺序一边遍历一边查表返回的始终是原数组下标。这也是这道题最适合哈希表而不是双指针的本质原因。但在面试里把双指针方案也提一嘴会有额外的加分效果你可以说“如果输入已经有序我会优先考虑双指针因为那样空间复杂度能降到O(1)但本题返回的是原数组下标所以哈希表更合适”。这种“根据约束条件动态选方案”的表达就是面试官想听的东西。5.3 工程中哈希表的实际使用场景除了刷题哈希表在工程代码里更是无处不在。缓存系统Redis的字典、数据库索引部分存储引擎、路由表、去重集合底层全是哈希表或哈希表的变体。理解了两数之和里的“空间换时间”你就能理解为什么缓存能大幅提升性能——因为把耗时查询的结果直接放进内存字典里一次命中就少一次IO。所以两数之和这题虽然短小但它把“设计一个能快速回答问题的辅助索引”这个思路塞进了你脑子里。这个思路是会复利的以后遇到任何“查找是否出现过”“查找对应关系”的问题你都会第一时间想到哈希表。6. 完整演练手把手跑一遍哈希表版两数之和最后我用一个完整的例子把整个思考过程和代码执行流程串起来。假设输入是nums [2, 7, 11, 15] target 9第一步建立一个空的哈希表record {}。第二步进入循环i 0num 2diff 9 - 2 7。查record里有没有7——没有所以把record[2] 0存进去。当前表{2: 0}。第三步i 1num 7diff 9 - 7 2。查record里有没有2——有下标是0。于是返回[0, 1]。代码执行到这里就结束了连后面两个元素都没遍历到。这其实就是哈希表方案的另一个隐藏优势它不一定需要遍历完整个数组运气好的话经常能提前返回。而暴力解必须全部条件都扫描完才能确定答案。再看一个稍微复杂点的输入nums [3, 2, 4] target 6注意这里的3 3其实也等于6但是数组里只有一个3所以不能用同一个元素两次。正确结果应该是[1, 2]因为2 4 6。跑一遍哈希表方案i0num3diff3。表里没有3存入{3:0}。i1num2diff4。表里没有4存入{3:0, 2:1}。i2num4diff2。表里有2下标1返回[1, 2]。完美避开3 3的错误答案正是因为遍历到第一个3的时候3还没被存进表里。如果先建表的话第一次循环查到3返回[0, 0]直接错误。这种“边查边存”的顺序保护就是这个方案最精妙的地方。把这两个例子自己动手跑一遍之后你对哈希表方案的每一步都会非常熟悉。下次再遇到哪怕闭着眼都能写出来。我自己当年就是从这道题开始养成了“写算法题之前先想数据结构”的习惯。后来不管是工作中设计缓存还是面试别人看候选人的代码都会下意识先问一句你的查找操作能不能更快哈希表不是万能的但当你需要“快速判断某个东西存不存在”的时候它通常是最直接的那个答案。这道两数之和就是帮你把这个条件反射练出来的第一站。