四数相加II：分组哈希如何将O(n^4)优化到O(n^2)

最近后台收到不少私信都是问我算法题怎么刷的。其中有一道标题看起来特别“朴素”的题目很多人第一反应就是写四个 for 循环然后稳稳卡在超时上——这就是 LeetCode 第 454 题“四数相加 II”。“四数相加”这个关键词在算法社区里的讨论度一直不低因为它难度中等偏易却把哈希表、空间换时间、暴力枚举优化这几个核心思想全串起来了。这篇文章我把这道题从头到尾拆一遍包括暴力解法为什么必挂、分组哈希怎么把 O(n^4) 压到 O(n^2)、以及面试官最爱追问的几种变体。适合正在准备算法面试的朋友也适合刚学完哈希表想找个实战案例上手的人。1. 先吃透题目四数相加II到底在考什么1.1 题目到底说了什么题目描述很简短给你四个长度都是 n 的整数数组 A、B、C、D统计所有满足 A[i] B[j] C[k] D[l] 0 的 (i, j, k, l) 四元组个数。官方样例是A [1, 2]B [-2, -1]C [-1, 2]D [0, 2]最终答案是 2。具体组合是1 (-2) (-1) 2 02 (-1) 2 (-1) ? 不对是 D 里的 02 (-1) (-1) 0 0反正就是两组下标组合满足条件。这里有一个极其关键的字眼只统计个数不要求输出具体组合。这句话决定了整道题的方向——题目要的是计数不是构造结果集所以很多复杂操作可以不做注意力应该全部集中在“怎么高效数出来”上。1.2 和题库18题“四数之和”的本质区别很多初学者看到“四数相加”就自动联想 LeetCode 第 18 题“四数之和”以为是一类题直接套排序 双指针 去重的模板结果把自己绕晕。这两道题表面同名本质完全不同。18 题是在同一个数组里选四个数四个下标彼此不能重复结果还不能有重复组合所以必须排序、双指针、跑去重逻辑。而 454 题是四个独立数组各取一个数四个下标天然来自不同数组任何一组下标都只能对应一个唯一四元组所以根本不存在“去重”这件事。这个区别直接改变解法路径。454 只需要做计数不需要做组合去重18 题那种排序双指针去重的思路拿到 454 来用属于杀鸡用牛刀还容易把代码写得又长又容易错。我见过不少人在面试现场卡在这一步就是由于先入为主套了模板没先问自己“题目里有没有重复下标的约束”。1.3 面试里的定位与考察点这道题如果出现在面试里考察的是三件事有没有“先暴力、再优化”的解题意识能不能自己推导出暴力不可行对哈希表的理解到位不到位能不能想到“存一侧、查另一侧”的分组策略面对变体问题数组长度不同、改成 K 个数组时能不能把思路迁移过去。我在带人的时候非常喜欢拿这道题做练手因为它从暴力到最优解的路径非常清晰中间没有特别偏门的数学技巧就是纯数据结构基本功。刷透这一题两数相加、三数相加、K-sum 这类“分组哈希”题型的思路基本就打通了。2. 从暴力枚举出发为什么O(n^4)的方案不可行2.1 四层循环的具体实现先看最直觉的写法四层循环逐个枚举所有组合def fourSumCount(A, B, C, D): count 0 for a in A: for b in B: for c in C: for d in D: if a b c d 0: count 1 return count这段代码正确性没有任何问题但它跑不动。题目里 n 最大可以到 200四层循环就是 200 * 200 * 200 * 200 16 亿次组合判断。Python 本身就慢16 亿次循环在 LeetCode 的评测环境下基本等于超时就算换成 C16 亿次加法加比较通常也要一到两秒以上很多题目的时间限制就是 1 秒照样超时。这里我想多说一句很多人刷题时不重视复杂度估算反正本地跑小样例通过了就提交结果一发 TLE超时就懵了。暴力解法不是不能写写出来是为了确认问题模型然后马上要想“这个规模下能不能落地”。2.2 O(n^4)到底是个什么概念用生活化的方式理解一下假设你每秒能手工数一个组合16 亿次组合你需要数 50 多年。即使CPU每秒能执行大约 10^8 到 10^9 次简单运算16 亿次循环也要十几秒到几十秒这已经超过了绝大多数在线评测系统的容忍范围。如果 n 进一步增大到 1000四层循环就是 10^12 次组合普通电脑要好几个小时才能跑完。这就是复杂度的现实意义——它不是装饰性的数学符号而是判断算法能不能落地的一把硬尺子。顺便回答一个高频问题计算复杂度时什么时候用 O什么时候用 Θ大 O 表达的是“上界”保证不会比这个量级更差而 Θ 表达的是“精确渐近”表示算法的上界和下界是同一个量级。这道题的暴力解法恰好上下界一致严格说可以写成 Θ(n^4)但工程和面试里说 O(n^4) 完全够用不必纠结。2.3 为什么常规剪枝在这里帮不上忙有朋友会问能不能加剪枝优化剪枝的核心逻辑是“提前判断某条路径没有希望直接跳过”但它通常依赖某种单调性或上下界。比如数组有序时如果当前数已经大于目标值后面的数更大可以直接 break。但 454 题的现状是四个数组无序且你枚举到 A[i]、B[j]、C[k] 时D 里的目标值是确定的可你不能保证 D 有序以后一定有一个快速退出条件因为你在枚举所有 D[l]不是二分查找某一个。即使你把四个数组都排序四层循环的层数也没变只是某些极端数据下能提前中断总体复杂度仍然是 O(n^4)。唯一能做的剪枝是利用极值范围判断比如四个数组的最大最小值区间的交集判断能不能凑出 0或者如果 A、B、C、D 里所有数同号那答案直接是 0。这类特判对随机数据有一点收益但救不了数量级上的问题。想要根治必须换思路。3. 核心解法哈希表分组聚合的完整拆解3.1 核心思路把四数相加降维成两数相加这道题最漂亮的地方在于一个恒等变形A[i] B[j] C[k] D[l] 0等价于 A[i] B[j] -(C[k] D[l])左边有 n * n 种组合右边也有 n * n 种组合。如果我们先把左边所有组合的和以及出现次数存进哈希表再遍历右边所有组合每得到一个和 S就去哈希表里找 -S 出现了几次把这些次数累加就是最终答案。这个“存一侧、查另一侧”的套路正是两数之和那类题的核心思想延伸。很多同学在学两数之和的时候记住了哈希表但只会在单个数组里用碰到多个数组就不知道怎么组合了。454 题就是对“分组哈希”思维最好的训练。3.2 第一遍遍历AB组合入表第一步遍历 A、B 的所有组合把 ab 作为 key出现次数作为 value 存进哈希表。hash_map {} for a in A: for b in B: hash_map[a b] hash_map.get(a b, 0) 1这里有个细节值得单独强调为什么存的是“次数”而不是“是否出现过”因为题目统计的是四元组个数。同一个 ab 的数值可以由多组不同的下标组合产生比如 A 里有 2 个 1B 里有 3 个 -1那 AB 等于 0 的组合就有 2×36 个。如果哈希表只存布尔值这 6 个组合就会被压缩成 1答案直接少算。我自己第一次写这题时就在这儿踩过坑只存了“这个和存不存在”结果样例跑不过。后来才意识到计数题的第一原则所有到哈希表的值要想清楚该存频次还是存坐标。3.3 第二遍遍历CD组合查表第二步遍历 C、D 的所有组合计算 target -(cd)然后去哈希表里取频次并累加count 0 for c in C: for d in D: target -(c d) count hash_map.get(target, 0) return count每查到一次出现次数就意味着有这么多组 (i, j) 能和当前这组 (k, l) 组合出合法四元组直接累加即可。这里必须用 get(target, 0)而不是直接 hash_map[target]。原因是 target 这个 key 在哈希表里可能根本不存在。Python 里直接取不存在的 key 会抛 KeyErrorC 的 std::map 里直接取不存在的 key 会自动插入一个默认值 0虽然不影响最终答案但会让哈希表越膨胀越厉害还掩盖了调试信息Java 则用 getOrDefault。这些语言差异刷题时经常遇到写之前先想清楚。3.4 为什么这个算法天然免去重这是面试官最爱追问的一个点你的解法里为什么不需要去重逻辑答案在于题目的数据结构。四元组 (i, j, k, l) 由四个独立数组的下标唯一决定。A[i] 和 B[j] 即使数值相同只要 i 或 j 不同它们就是不同的组合。哈希表里存的频次天然就是“不同下标组合的数量”而 C、D 侧遍历时一组一组枚举也天然区分不同下标组合。用例子说明A 有 2 个 1B 有 3 个 -1C、D 各只有 1 个 0 元素。那么 AB0 的频次是 6CD0 的频次是 1答案直接是 6。这里没有任何“去掉相同数值组合”的必要性因为下标不同结果就不同。“去重”这件事只在同一个数组中选元素时才会出现四个独立数组天然绕开了这个麻烦。3.5 复杂度分析与方案对比分组哈希的时间复杂度建表阶段双重循环遍历 A、BO(n^2)查表阶段双重循环遍历 C、DO(n^2)总时间O(n^2)额外空间哈希表最多存 n^2 个键值对O(n^2)n200 时暴力法是 16 亿次运算分组哈希是 4 万次组合构建 4 万次查询总共 8 万次操作毫秒级出结果。空间上 4 万条记录的内存也就几十 KB完全可接受。方案时间复杂度空间复杂度n200时量级暴力四层循环O(n^4)O(1)16亿次分组哈希O(n^2)O(n^2)约8万次这就是典型的空间换时间。哈希表额外占了 O(n^2) 的内存换来了时间从四次方降到二次方的数量级提升。在很多场景下这种交换是非常划算的。4. 代码落地Python/C实现与细节4.1 Python实现与dict.get的救场完整 Python 解法如下def fourSumCount(A, B, C, D): sum_ab {} for a in A: for b in B: sum_ab[a b] sum_ab.get(a b, 0) 1 ans 0 for c in C: for d in D: ans sum_ab.get(-(c d), 0) return ans也有写法是用 collections.Counter 一行生成 sum_abfrom collections import Counter sum_ab Counter(a b for a in A for b in B) ans sum(sum_ab.get(-(c d), 0) for c in C for d in D)Counter 的写法更简洁但我个人在面试时更推荐手写 dict.get 版本。第一手写版逻辑一目了然不会让面试官觉得你在背模板第二实测在 n200 的数据规模下手写 dict 通常比 Counter 构造略快一点因为 Counter 内部还包含额外的通用计数逻辑第三手写版更容易扩展到本章后面说的变体场景。4.2 C实现与整型溢出提醒C 版本int fourSumCount(vectorint A, vectorint B, vectorint C, vectorint D) { unordered_maplong long, int hash_ab; hash_ab.reserve(A.size() * B.size()); for (int a : A) { for (int b : B) { hash_ab[(long long)a b]; } } int ans 0; for (int c : C) { for (int d : D) { long long target -(long long)c - d; auto it hash_ab.find(target); if (it ! hash_ab.end()) { ans it-second; } } } return ans; }这里有几个 C 专属的注意点为什么 key 用 long long因为 vector 里的 int 最大值约 21 亿两个 int 相加可能溢出 int 范围。虽然题目测试数据不一定踩到这个边界但用 long long 是零成本的防御。为什么先 reserve 预留桶因为 unordered_map 扩容是有代价的。我们预先知道最多会存 n^2 个 keyreserve 之后避免重复 rehash实测能减少约 10% 左右的耗时。查表时用 find 而不是直接 hash_ab[target] 访问。原因前面提过operator[] 对不存在 key 会自动插入默认值 0从而污染哈希表。4.3 边界条件处理清单刷题时边界条件一定要覆盖全否则面试官随便给一组特殊输入就可能翻车。我整理了一个清单四个数组中有空数组循环体不执行build 表和查询都不发生返回 0正确。所有数组只有 1 个元素AB 只有 1 个值CD 也只有 1 个值查表一次出结果。所有元素都是 0AB0 的频次是 n^2CD0 的频次是 n^2答案是 n^4。哈希表同样能正确算出来。元素极大或极小Python 自动大整数没有溢出问题C/Java 需要把求和类型提升到 long long。边界条件不复杂但很容易被忽略。比如空数组时如果代码里写死了 A[0] 之类的访问就直接崩了。养成习惯先处理空数组再走主逻辑。5. 进阶变体面试官追问怎么答5.1 四个数组长度不同怎么办如果四个数组长度不一样假设 A、B 的组合数是 LC、D 的组合数是 R分组哈希的总时间无论如何都是 O(L R)因为建表要扫一边的所有组合查询要扫另一边的所有组合。所以真正值得优化的是内存。结论很干净把组合数较小的两个数组入表组合数较大的数组用来遍历。因为查询是 O(1)遍历侧组合再大也无所谓但入表侧组合越大哈希表占用内存越大。选小侧入表内存更省时间不变。举个例子A、B 各长 200C、D 各长 1000。如果 AB 入表哈希表 4 万条遍历 CD 是 100 万次查询反过来 CD 入表哈希表 100 万条遍历 AB 是 4 万次查询。总时间都是 104 万次左右但内存差了几十倍。所以“小组合入表”是更优策略。5.2 如果题目要求返回所有具体四元组如果题目从“统计个数”变成“打印所有具体四元组”就不能只存频次了。你得为每个 AB 的和存下所有具体的 (i, j) 对然后在遍历 CD 时把所有匹配的 AB 坐标拼接起来输出。但这里有一个关键认知输出规模本身可能高达 O(n^4)。也就是说不管用什么算法只要结果本身有那么多就一定会慢到无法接受。这正是 454 题只问数量而不是问具体组合的原因——数量可以用 O(n^2) 的哈希表压缩组合构造的复杂度则是另一回事。面试时如果能主动指出“输出规模是瓶颈”面试官会认同你对复杂度的理解。5.3 扩展成K个数组相加K-sum变体通式把四个数组推广为 K 个数组每个数组长度 n问有多少组下标组合使 K 个数相加等于 0。通用思路是把 K 个数组分成两组一组 m 个数组入表另一组 K-m 个数组查表时间复杂度 O(n^m n^(K-m))。要让这个表达式最小最佳分组是 m 尽量接近 K/2。K 为偶数时两边各 K/2 个数组总复杂度 O(n^(K/2))K 为奇数时比如 5 个数组可以 2 个入表、3 个查表总复杂度 O(n^3)虽然没有完全对称但也远优于直接暴力 O(n^5)。这个推导过程能答出来基本上 K-sum 一类的变形题都难不倒你。5.4 分组哈希在真实业务里的影子别以为这类技巧只能应付面试。我实际做过一个多路日志关联统计的小工具场景是把用户访问记录和订单记录按“用户ID 日期”的组合维度关联起来统计“同一天既访问又下单”的次数。说白了就是把一批记录的 (user, date) 组合入表再遍历另一批记录去查表。这和四数相加II的分组哈希思维一模一样。推荐系统里的特征交叉统计也是类似的道理。两个特征组合的共现次数常常就是先枚举一侧特征对建立频次表再用另一侧查表累加。所以这道题不只是在刷题平台上有用遇到多维匹配、多路计数类问题时这套思路可以直接搬过去用。6. 调试踩坑与实测心得6.1 常见问题速查表我在学习和带人过程中收集了这道题最常见的几个坑整理成速查表问题现象原因解法答案翻倍统计结果比正确答案大两侧都建表且互相查组合被重复计数固定一侧入表另一侧只负责查询报 KeyErrorPython 环境直接报错目标 key 不存在却直接取下标用 get(target, 0)查询后哈希表莫名变大内存膨胀、调试困难C 里用 operator[] 访问不存在 key先 find 再取值溢出导致错误答案极端数据下结果是负数或异常int 相加溢出使用 long long套用18题去重模板代码冗长且不好调整没意识到四个独立数组天然免去重回归分组哈希计数思路其中“答案翻倍”是我自己犯过的错。第一次写这题时我把 AB 和 CD 都存进了哈希表然后在两边各自再建一个查询循环结果每个组合都被查了两遍最终答案正好是真实值的两倍。这个错误特别隐蔽因为小样例凑巧能通过数据一多就露馅。后来总结出一个很实用的检查方法写完代码后在脑内走一遍只有一个元素的最简单用例看每一步的计数是否符合预期。6.2 我踩过的其他坑与调试技巧除了上面这些我还遇到过把题目读错的情况——把“四个数组各取一个数”理解成“同一个数组里取四个数”然后花了不少时间写排序双指针加去重。最后发现代码很长跑出来结果对不上。这个教训提醒我拿到题目先读三遍搞清楚下标来源再动笔写码。调试时还有一个值得分享的小技巧如果感觉答案不对先缩小数据规模。把每个数组都缩到长度为 2然后手动枚举出所有组合对比程序输出。这道题的最优解法虽然代码短但“计数逻辑”一旦写错小样本下很容易暴露。别一上来就用 n200 的大数据测那样只会得到一个“答案不对”的模糊信号很难定位问题。6.3 实测性能与可能的微优化在 LeetCode 的环境下n200 时 Python 的 dict.get 版本跑完基本就是毫秒级别完全不用担心性能。C 版本加上 reserve 之后比不加 reserve 大概能快 10% 左右但这点提升在这个数据规模下并没有实质影响。真正值得投入精力的是把算法骨架写对而不是纠结微优化。把 O(n^4) 降到 O(n^2) 才是这道题的核心剩下的操作都是锦上添花。最后说点个人体会。四数相加II这道题我反复刷过很多遍每次带新人或者面候选人时都喜欢拿出来讲因为它从暴力枚举到哈希分组从单题到 K-sum 通式整个解题链条特别完整非常适合作为“用已知问题解决未知问题”的训练样本。如果你第一反应只想到四层 for 循环完全正常绝大多数人都是这样起步的。但如果你能写出分组哈希并且把“为什么不用去重”“为什么是存一侧查另一侧”讲清楚那面试官基本就能确认你的算法功底是扎实的。下次遇到多路匹配、多维计数这类需求记得先想想能不能拆成两两组合再做决定。这道题教会我的就是这句话。