四数相加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 = 0
• 2 + (-1) + 2 + (-1) ? 不对，是 D 里的 0：2 + (-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 的评测环境下基本等于超时；就算换成 C++，16 亿次加法加比较通常也要一到两秒以上，很多题目的时间限制就是 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 第一遍遍历：A+B组合入表

第一步，遍历 A、B 的所有组合，把 a+b 作为 key，出现次数作为 value 存进哈希表。

hash_map = {} for a in A: for b in B: hash_map[a + b] = hash_map.get(a + b, 0) + 1

这里有个细节值得单独强调：为什么存的是“次数”而不是“是否出现过”？因为题目统计的是四元组个数。同一个 a+b 的数值可以由多组不同的下标组合产生，比如 A 里有 2 个 1，B 里有 3 个 -1，那 A+B 等于 0 的组合就有 2×3=6 个。如果哈希表只存布尔值，这 6 个组合就会被压缩成 1，答案直接少算。

我自己第一次写这题时就在这儿踩过坑，只存了“这个和存不存在”，结果样例跑不过。后来才意识到计数题的第一原则：所有到哈希表的值，要想清楚该存频次还是存坐标。

3.3 第二遍遍历：C+D组合查表

第二步，遍历 C、D 的所有组合，计算 target = -(c+d)，然后去哈希表里取频次并累加：

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 会抛 KeyError；C++ 的 std::map 里直接取不存在的 key 会自动插入一个默认值 0，虽然不影响最终答案，但会让哈希表越膨胀越厉害，还掩盖了调试信息；Java 则用 getOrDefault。这些语言差异刷题时经常遇到，写之前先想清楚。

3.4 为什么这个算法天然免去重

这是面试官最爱追问的一个点：你的解法里为什么不需要去重逻辑？

答案在于题目的数据结构。四元组 (i, j, k, l) 由四个独立数组的下标唯一决定。A[i] 和 B[j] 即使数值相同，只要 i 或 j 不同，它们就是不同的组合。哈希表里存的频次，天然就是“不同下标组合的数量”，而 C、D 侧遍历时一组一组枚举，也天然区分不同下标组合。

用例子说明：A 有 2 个 1，B 有 3 个 -1，C、D 各只有 1 个 0 元素。那么 A+B=0 的频次是 6，C+D=0 的频次是 1，答案直接是 6。这里没有任何“去掉相同数值组合”的必要性，因为下标不同，结果就不同。“去重”这件事只在同一个数组中选元素时才会出现，四个独立数组天然绕开了这个麻烦。

3.5 复杂度分析与方案对比

分组哈希的时间复杂度：

• 建表阶段：双重循环遍历 A、B，O(n^2)
• 查表阶段：双重循环遍历 C、D，O(n^2)
• 总时间：O(n^2)
• 额外空间：哈希表最多存 n^2 个键值对，O(n^2)

n=200 时，暴力法是 16 亿次运算，分组哈希是 4 万次组合构建 + 4 万次查询，总共 8 万次操作，毫秒级出结果。空间上 4 万条记录的内存也就几十 KB，完全可接受。

这就是典型的空间换时间。哈希表额外占了 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_ab：

from 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 版本。第一，手写版逻辑一目了然，不会让面试官觉得你在背模板；第二，实测在 n=200 的数据规模下，手写 dict 通常比 Counter 构造略快一点，因为 Counter 内部还包含额外的通用计数逻辑；第三，手写版更容易扩展到本章后面说的变体场景。

4.2 C++实现与整型溢出提醒

C++ 版本：

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { unordered_map<long 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 个 key，reserve 之后避免重复 rehash，实测能减少约 10% 左右的耗时。
• 查表时用 find 而不是直接 hash_ab[target] 访问。原因前面提过：operator[] 对不存在 key 会自动插入默认值 0，从而污染哈希表。

4.3 边界条件处理清单

刷题时边界条件一定要覆盖全，否则面试官随便给一组特殊输入就可能翻车。我整理了一个清单：

• 四个数组中有空数组：循环体不执行，build 表和查询都不发生，返回 0，正确。
• 所有数组只有 1 个元素：A+B 只有 1 个值，C+D 也只有 1 个值，查表一次出结果。
• 所有元素都是 0：A+B=0 的频次是 n^2，C+D=0 的频次是 n^2，答案是 n^4。哈希表同样能正确算出来。
• 元素极大或极小：Python 自动大整数没有溢出问题；C++/Java 需要把求和类型提升到 long long。

边界条件不复杂，但很容易被忽略。比如空数组时，如果代码里写死了 A[0] 之类的访问，就直接崩了。养成习惯：先处理空数组，再走主逻辑。

5. 进阶变体：面试官追问怎么答

5.1 四个数组长度不同怎么办

如果四个数组长度不一样，假设 A、B 的组合数是 L，C、D 的组合数是 R，分组哈希的总时间无论如何都是 O(L + R)，因为建表要扫一边的所有组合，查询要扫另一边的所有组合。所以真正值得优化的是内存。

结论很干净：把组合数较小的两个数组入表，组合数较大的数组用来遍历。因为查询是 O(1)，遍历侧组合再大也无所谓，但入表侧组合越大，哈希表占用内存越大。选小侧入表，内存更省，时间不变。

举个例子：A、B 各长 200，C、D 各长 1000。如果 A+B 入表，哈希表 4 万条，遍历 C+D 是 100 万次查询；反过来 C+D 入表，哈希表 100 万条，遍历 A+B 是 4 万次查询。总时间都是 104 万次左右，但内存差了几十倍。所以“小组合入表”是更优策略。

5.2 如果题目要求返回所有具体四元组

如果题目从“统计个数”变成“打印所有具体四元组”，就不能只存频次了。你得为每个 A+B 的和存下所有具体的 (i, j) 对，然后在遍历 C+D 时把所有匹配的 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 常见问题速查表

我在学习和带人过程中，收集了这道题最常见的几个坑，整理成速查表：

其中“答案翻倍”是我自己犯过的错。第一次写这题时，我把 A+B 和 C+D 都存进了哈希表，然后在两边各自再建一个查询循环，结果每个组合都被查了两遍，最终答案正好是真实值的两倍。这个错误特别隐蔽，因为小样例凑巧能通过，数据一多就露馅。后来总结出一个很实用的检查方法：写完代码后在脑内走一遍只有一个元素的最简单用例，看每一步的计数是否符合预期。

6.2 我踩过的其他坑与调试技巧

除了上面这些，我还遇到过把题目读错的情况——把“四个数组各取一个数”理解成“同一个数组里取四个数”，然后花了不少时间写排序双指针加去重。最后发现代码很长，跑出来结果对不上。这个教训提醒我：拿到题目先读三遍，搞清楚下标来源，再动笔写码。

调试时还有一个值得分享的小技巧：如果感觉答案不对，先缩小数据规模。把每个数组都缩到长度为 2，然后手动枚举出所有组合，对比程序输出。这道题的最优解法虽然代码短，但“计数逻辑”一旦写错，小样本下很容易暴露。别一上来就用 n=200 的大数据测，那样只会得到一个“答案不对”的模糊信号，很难定位问题。

6.3 实测性能与可能的微优化

在 LeetCode 的环境下，n=200 时 Python 的 dict.get 版本跑完基本就是毫秒级别，完全不用担心性能。C++ 版本加上 reserve 之后，比不加 reserve 大概能快 10% 左右，但这点提升在这个数据规模下并没有实质影响。

真正值得投入精力的是把算法骨架写对，而不是纠结微优化。把 O(n^4) 降到 O(n^2) 才是这道题的核心，剩下的操作都是锦上添花。

最后说点个人体会。四数相加II这道题我反复刷过很多遍，每次带新人或者面候选人时都喜欢拿出来讲，因为它从暴力枚举到哈希分组，从单题到 K-sum 通式，整个解题链条特别完整，非常适合作为“用已知问题解决未知问题”的训练样本。如果你第一反应只想到四层 for 循环，完全正常，绝大多数人都是这样起步的。但如果你能写出分组哈希，并且把“为什么不用去重”“为什么是存一侧查另一侧”讲清楚，那面试官基本就能确认你的算法功底是扎实的。下次遇到多路匹配、多维计数这类需求，记得先想想能不能拆成两两组合，再做决定。这道题教会我的，就是这句话。