两数之和为什么要边查边存:哈希把两层循环压成一层
两数之和要在数组里找两个不同下标,使它们的和等于目标值。暴力枚举所有配对是 O(n²),而哈希表把“找互补数”变成一次查表,平均 O(n)。很多人背下了“用字典存值到下标的映射”,却常把先存后查写反,遇到两个相同元素就返回同一个下标;也有人把平均 O(1) 当成严格 O(1),忽略了碰撞退化与额外内存。读完你能讲清一遍扫描为什么必须“先查后存”,分清哈希与排序双指针各自的适用边界,并知道怎样用边界用例把实现钉死。
是什么
两数之和是给定一个数组 nums 和一个目标值 target,找出两个不同下标 i、j,使 nums[i] + nums[j] == target。最直白的做法是两层循环枚举所有配对,时间 O(n²);哈希解法把“找另一个数”从扫描整个数组变成一次查表,平均时间 O(n)。一句话直觉:不要让每个数都去和全场握手,而是每个数进门时先在登记簿上写一笔,后来的人只问登记簿“我的互补数来过没有”。
这道题是 LeetCode 第 1 题,也是“空间换时间”最经典的入口。它的影子遍布工程:频次统计、去重、按 key 找对象、缓存索引,本质都是先建一张查找表,把线性扫描换成常数级定位。
核心原理
暴力解的瓶颈不是加法慢,而是配对数量太多:n 个元素能组成约 n²/2 对,全部检查一遍就是 O(n²)。换一个视角,对当前元素 x,其实不需要知道“谁能和我配对”,只需要知道“target - x 之前出现过没有”。前者要求扫描整个数组,后者只要求一次查表。
于是维护一个哈希表,键是已经扫描过的元素值,值是它的下标。每走到 x,先算 need = target - x,查表里有没有 need;有就立即返回两个下标,没有就把 x 和当前下标写进表里。整个过程只扫一遍数组,每个元素做一次查找加一次插入。
这里用字典而不是集合,是因为题目要返回下标:集合只能回答“在不在”,字典还能回答“在哪”。如果只需要判断是否存在这样一对数,用集合就够,内存还能再省一点。
这里最容易被忽略的是顺序:必须“先查后存”,不能“先存后查”。如果先把 x 自己写进表里,再查 need,当 target == 2 * x 时,need 恰好等于 x,查到的就是刚写进去的自己,返回值会出现两个相同下标。先查后存保证表里只有 j < i 的元素,下标天然不同。
def two_sum(nums, target):
seen = {} # 值 -> 下标
for i, x in enumerate(nums):
need = target - x
if need in seen: # 只查已经进场的元素
return [seen[need], i]
seen[x] = i # 查完再登记自己
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
print(two_sum([3, 3], 6)) # [0, 1]
print(two_sum([3, 2, 3], 6)) # [0, 2]
拿 [2, 7, 11, 15]、target = 9 走一遍:i = 0 时 need = 7,表是空的,登记 2 → 0;i = 1 时 need = 2,命中下标 0,立刻返回 [0, 1]。全过程只看了两个元素,后面的 11 和 15 根本没被访问。这也是一遍扫描比“先把所有元素装进表、再逐个查互补数”更划算的地方:后者每个元素都要写一次,还得额外判断不能命中自己,边界更容易写错;前者把候选集合限制在当前元素之前的前缀里,正确性反而更好论证。
哈希表之所以快,是因为它不靠逐个比较找键,而是用哈希函数把键映射到桶位,平均一次就能定位。插入会触发扩容,但容量按倍数增长、旧元素重新分布,均摊到每次插入仍是 O(1)。代价是额外空间 O(n),以及哈希函数质量、负载因子这些工程变量。所有键都撞进同一个桶时,单次查找退化为 O(n),整体回到 O(n²);Java 8 的 HashMap 在桶内节点过多时把链表转成红黑树,正是为了把这种最坏情况压到 O(log n)。
也可以换一条路:先排序,再用左右双指针对撞,时间 O(n log n)、额外空间 O(1)。它更省内存,但排序会打乱原始下标;题目要求返回原下标时,还得把“值 + 原下标”一起排序,重复值的处理也会变复杂。数组本来就有序时,双指针反而是 O(n) 且几乎不占额外空间。
常见考点与误区
- 误区一:先存后查也能过。 面试官给出
[3, 3]、target = 6,先存后查会返回[0, 0],同一个元素被用了两次。正确写法是先查后存;如果坚持两遍扫描,则必须显式判断命中的下标不等于当前下标。 - 误区二:把平均 O(1) 说成严格 O(1)。 哈希查找的 O(1) 是平均或均摊意义上的,最坏是 O(n)。能补充“碰撞严重时整体退化为 O(n²)”“扩容有均摊成本”,比只背结论更能体现理解。
- 考点三:有重复元素时,返回一组还是全部。 多数题目保证答案唯一,命中即可返回;若要输出所有下标对,一遍扫描查到一个就停会漏解,需要先统计频次或排序后去重,复杂度还要算上输出规模。
- 考点四:排序加双指针能不能替代哈希。 能,但不等价:时间从平均 O(n) 变成 O(n log n),换来更低的内存占用;一旦排序就丢失原下标,若题目要求下标,必须额外携带下标信息。
- 考点五:什么能当键。 列表、字典等可变对象不可哈希,不能直接做键;浮点数做键要小心精度以及
-0.0、NaN的特殊行为。用哈希之前先确认元素类型是否可哈希、相等语义是否符合预期。
实践建议
- 默认采用一遍扫描、先查后存。空间是 O(n),元素上百万时要先估算内存:哈希表每个条目都有固定开销,实际占用往往明显大于“元素个数 × 单个元素大小”。
- 按需求选型:要一组解且要原下标,用哈希;数组已排序或允许排序且只要值,用双指针;内存极紧、能接受 O(n log n),再考虑排序。
- 在 Go 里用
make(map[int]int, len(nums))预留容量,在 Java 里给HashMap设一个接近元素规模的初始容量,都能减少扩容与重新哈希;容量按负载因子留余量即可,不必精确到个位。 - 不要原地排序调用方传入的数组。副作用很难排查,需要排序时先拷贝,或把下标一起打包。
- 自己实现哈希表时不要用弱哈希直接处理不可信输入,否则可能被构造出大量碰撞拖垮服务;主流语言的字典通常已做哈希随机化。
- 如果数据是流式的、不能一次全部载入内存,哈希表仍要保存所有已见元素,内存不会凭空消失;这时应分批处理或改用外部排序后归并,不要假设内存无限。
- 边界用例至少覆盖:空数组、只有一个元素、两个相同值、负数与 0、
target为 0、无解。这些用例比正例更容易暴露“先存后查”写反的问题。
一句话总结:哈希加速的关键不是查得快,而是把“找互补数”变成“查已出现过的数”,并用先查后存守住下标不重复。