前两天在算法群里看到有人问四数相加Ⅱ底下一波回复全是“四数之和嘛排序加双指针不就行了”“先 sort 再固定两个数呀”看得我血压直接上来了。四数相加Ⅱ和四数之和名字就差两个字解法方向却南辕北辙一个是哈希表的两两分组计数一个是排序加双指针的去重搜索。如果你正在准备面试或者刚开始刷哈希表专题这道题几乎是必练题——它是“空间换时间”思想最干净的例题之一也是把复杂度从 O(n^4) 压到 O(n^2) 的经典示范。这篇文章我会从题目差异讲起把暴力解法为什么不可行、两两分组的数学直觉、Python 和 C 的完整实现、面试追问里的加分点以及我自己实际提交时踩过的坑一次性讲透。1. 四数相加Ⅱ和四数之和名字像但考点完全不一样1.1 先把题目读清楚四数相加Ⅱ的题面很短给定四个整数数组nums1、nums2、nums3、nums4四个数组长度相等记为n。要求统计所有满足nums1[i] nums2[j] nums3[k] nums4[l] 0的下标组合(i, j, k, l)的数量。注意这里的措辞统计的是下标四元组的数量。nums1[0] 1和nums1[1] 1是两个不同的下标哪怕值相等只要下标不同对应的组合就要分别计数。力扣原题给了三个约束n最大为 200数组元素范围在[-2^28, 2^28]最终答案保证在 32 位整数范围内。这三个数字不是摆设后面分析复杂度和溢出时全都用得上。很多人的第一道坎就在这里题面只有一句话但“计数”和“去重”两个词的差别直接决定解法方向。如果你脑子里还是“四个数找一找等于零的组合”大概率会把这题做成四数之和的翻版然后一头栽进去。1.2 和四数之和的本质差异我把两个问题放在一起对比过差异一目了然维度四数之和一个数组四数相加Ⅱ四个数组数据来源一个数组里取四个下标四个数组各取一个下标目标找出所有和为 target 的四元组只统计和为 0 的四元组数量是否去重必须去重值相同算重复不需要去重下标不同都算主流解法排序 双指针 / 递归固定哈希表两两分组时间复杂度O(n^3)O(n^2)为什么差异这么大因为问题的难点根本不在同一个地方。四数之和里四个下标来自同一个数组天然有“下标不能重叠”的限制而且值相同的四元组会重复出现你得费劲心思去重所以排序加双指针是最顺手的工具。四数相加Ⅱ里四个数组彼此独立下标之间没有任何冲突问题核心从“找集合”变成了“统计匹配数量”哈希表计数就成了最自然的工具。1.3 这道题真正考察的能力面试官出这题不是想看你背没背过模板而是考察一条完整的能力链能不能一眼看出四层循环不可接受能不能想到用哈希表把查询从 O(n) 降到 O(1)能不能自己推出“2 2 分组”而不是“3 1 分组”能不能在被追问“空间为什么多了这么多”时给出清晰的权衡分析。这些能力层层递进。大多数人的水平卡在第二点知道用哈希表但只会存一个数组去查三个数组复杂度是 O(n^3)。能走到第三点的才是真的理解了这道题。先把一个观念立住四数相加Ⅱ 两两分组求和 哈希表互补查找。后面所有讨论都围绕这句话展开。2. 从四层循环到两两分组复杂度是怎么一步步降下来的2.1 暴力四层循环到底卡在哪先写一个逻辑完全正确的暴力版本def four_sum_count_bruteforce(nums1, nums2, nums3, nums4): n len(nums1) ans 0 for i in range(n): for j in range(n): for k in range(n): for l in range(n): if nums1[i] nums2[j] nums3[k] nums4[l] 0: ans 1 return ans这段代码没有任何错误但它跑不完。按力扣约束n 200代入循环次数是200^4 1.6e9。Python 一秒大概能跑几千万次到一亿次简单操作1.6 亿次已经是秒级16 亿次意味着你要等几十秒甚至几分钟。力扣这道题的时间限制通常是 2 秒暴力必挂。更扎心的是如果某家公司的笔试把n悄悄改成 2000那循环次数直接变成2000^4 1.6e13。这个量级已经不能用“慢一点”来形容而是物理上不可行——哪怕一秒跑十亿次也要四五个小时。所以我一直跟别人说写代码之前先估复杂度这道题就是最好的反面教材。用个生活化的类比四个人各拿一副牌你要逐个尝试每一手组合能不能凑出目标点数组合数量是天文数字老手的做法是先算清其中两个人的所有手牌组合做成一张对照表再去配另外两个人的手牌。2.2 用哈希表先砍掉一层循环如果暂时不做两两分组只用一个哈希表能优化到什么程度思路是把nums4里每个值出现的次数存进哈希表剩下三层循环枚举i, j, k每次计算nums1[i] nums2[j] nums3[k]的相反数去哈希表里查它出现过几次累加进答案。def four_sum_count_3plus1(nums1, nums2, nums3, nums4): counter {} for v in nums4: counter[v] counter.get(v, 0) 1 ans 0 for a in nums1: for b in nums2: for c in nums3: need -(a b c) ans counter.get(need, 0) return ans时间复杂度是 O(n^3)空间复杂度 O(n)。n 200时循环次数是8e6Python 勉强能跑C 轻松很多。那为什么标准答案还要继续优化成 O(n^2)因为 31 只是“恰好能过这道题”22 才是“任何数据规模下都稳”。面试官把约束改一改O(n^3) 立刻现原形。刷算法题讲究的是思路要站在 general 的高度不能被某一个数据范围惯坏。2.3 为什么是 22而不是 3131 已经是三循环22 是两个二重循环并行复杂度从 O(n^3) 降到 O(n^2)。一个简单的不等式就能说明问题当 n 足够大时n^3 的增长速度远快于 n^2所以只要内存代价能接受分组越均衡越好。这里其实藏着一个更一般的原则两个规模相同的问题合并比一大一小合并更高效。4 拆成 13总工作量是 O(n^3)因为三个人那组必然成为瓶颈拆成 22两边工作量各是 O(n^2)总量级直接降一档。我用一个团队协作的类比四个人写报告一组分一个人、另一组分三个人三个人那组一定拖后腿改成两组各两个人总时间才可能最短。哈希表版的 22 就是这个道理——建表一侧做 n^2 次求和查询一侧也做 n^2 次求和两边均衡总量最小。到这里解题框架已经清楚了枚举nums1和nums2的所有两两组合把a b的和作为 key出现次数作为 value存入哈希表。枚举nums3和nums4的所有两两组合计算-(c d)在哈希表里查询并累加次数。3. 核心实现哈希表存前两组查询后两组3.1 Python 实现与逐行拆解我最常用的 Python 版本用到了Counter读起来最直观from collections import Counter def four_sum_count(nums1, nums2, nums3, nums4): # 第一步统计 nums1 nums2 的所有两两和以及每个和出现的次数 sums Counter() for a in nums1: for b in nums2: sums[a b] 1 # 第二步枚举 nums3 nums4 的每个两两和去查互补值 ans 0 for c in nums3: for d in nums4: need -(c d) ans sums[need] return ans这里有个细节值得说一下Counter是字典的计数包装访问不存在的 key 会返回 0所以sums[a b] 1不会抛KeyError这是Counter自带__missing__实现带来的便利。不过面试时我更推荐写纯字典版本因为它的每一步都展示了原理不会被面试官误认为“只会调包”def four_sum_count(nums1, nums2, nums3, nums4): sums {} for a in nums1: for b in nums2: s a b sums[s] sums.get(s, 0) 1 ans 0 for c in nums3: for d in nums4: ans sums.get(-(c d), 0) return ans逐行拆解建表循环里sums.get(s, 0) 1的意思是如果s已经在表里取旧次数加一如果不在取 0 加一等价于初始化成 1。这一行同时完成了“去重计数”和“避免 KeyError”两件事。查询循环里need -(c d)等价于0 - (c d)但写负号更直观。你要找的是“能和当前组合凑成 0 的那个数”直接取相反数就好。sums.get(need, 0)如果查不到返回 0累加后不影响答案。n 200时两个二重循环各自只有 4 万次操作整个过程几乎瞬间出结果。这也是 22 方案最明显的体验数据量小的题目看不出差距但复杂度分析告诉我们它经得起放大。3.2 C 实现与 unordered_map 的细节如果面试要求写 C我的模板是这样#include unordered_map using namespace std; class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_maplong long, int sums; for (int a : nums1) for (int b : nums2) sums[(long long)a b]; int ans 0; for (int c : nums3) for (int d : nums4) { long long target -((long long)c d); auto it sums.find(target); if (it ! sums.end()) ans it-second; } return ans; } };几个容易在面试时被追问的点为什么 key 用long long按题目约束a b的最大绝对值是2^29 ≈ 5.37e8int完全放得下。但如果出题人稍微改一下数据范围比如把元素上限从2^28改成2^30a b就会溢出int。用long long是防御性写法不亏。为什么用find而不是operator[]C 里unordered_map的operator[]在 key 不存在时会插入一个默认值 0这是很多人的坑。如果你写if (sums[target]) ans sums[target]第一次查询不存在的 key 时哈希表里会多出一堆垃圾键。虽然在“只累加答案”的场景下逻辑还能保持正确但表被污染了后续任何遍历操作都会看到根本不存在的组合内存和性能也跟着受损。用find查到迭代器再取it-second干净利落。为什么不用mapmap底层是红黑树每次操作 O(log n)这题只需要存在性和计数键不需要有序unordered_map平均 O(1)4 万级别的操作量级下差距不明显但 n 一旦放大差距就出来了。3.3 一个容易忽略的优化数组长度不平衡时题目保证四个数组等长但如果你在写企业笔试题遇到长度不一样的变体怎么办我的习惯是把较短的数组放在建表层。因为哈希表的大小取决于建表侧的组合数量把短数组放进去表更小内存更省查询侧即使数组很长也只是多跑几次循环不影响表的大小。这个细节不算什么惊天动地的优化但面试时主动说出来说明你真的理解了哈希表两侧的角色分工比闷头写完全程然后干等提问要强。4. 复杂度分析与边界情况别只写出 AC 就交差4.1 复杂度到底怎么算内存到底花在哪三种方案放在一起对比差距非常直观算法时间复杂度空间复杂度n200 时的大致操作数暴力四层循环O(n^4)O(1)1.6e9三层循环 哈希表O(n^3)O(n)8e6两两分组 哈希表O(n^2)O(n^2)4e4 4e4两两分组方案的时间复杂度好算建表是一个二重循环O(n^2)查询是另一个二重循环O(n^2)加起来 O(n^2)。空间上最坏情况是nums1 nums2的所有两两和互不相同哈希表里存在 n^2 个键。n 200时是 4 万个键微不足道。但如果 n 涨到 2000就是 400 万个键按每个键值对几十字节计算内存会到几百 MB 级别这时候就要认真权衡了。面试官特别喜欢在这个位置追问“22 虽然快但空间大了你能接受吗”这个问题没有标准答案关键看你能否说出权衡逻辑在 n 较小或内存充裕时22 无脑选在 n 巨大且内存受限时可以退回 31 的 O(n^3)/O(n)用时间换空间。能说出这一层比背出任何一行代码都加分。4.2 边界条件清单我每次写完这类题都会专门过一遍边界这题的清单如下空数组n 0循环不执行函数返回 0代码天然正确。有些平台的版本允许空数组这点可以放心。全零数组每个数组里全是 0任意四个元素相加都是 0答案是n^4。拿n 200代入答案是 16 亿正好卡在 32 位整数上限 21.47 亿之内——这解释了为什么题目敢写“答案保证在 32 位整数内”。重复值哈希表的 value 记录出现次数正好覆盖重复下标组合的情况不需要额外处理。负数哈希键就是整数本身负数一样当 key没有任何坑。4.3 关于溢出的严谨讨论Python 用户写这道题非常舒服因为int不会溢出。但用 C 或 Java 就得留个心眼。按官方约束a b和c d的最大绝对值是 5.37 亿取反之后依然在int安全范围内。所以严格来说用int做 key 也能过。我为什么坚持long long因为我见过有人把题目改成[-2^30, 2^30]的变体int直接溢出变成负数答案怎么跑都不对。面试时主动补一句“官方数据 int 够但我会用 long long 防御”是典型的加分操作。还有一个容易忽略的点答案本身是 n^4 量级。官方 n200 时200^4 1.6e9int 装得下可一旦 n 被改成 1000答案就是 1e12必须long long。所以返回值的类型也得跟着数据范围走。5. 从四数相加到 K 数相加一套方法能不能通吃5.1 通用折半分组框架刷完这道题之后我认真想过一个问题如果题目变成 K 个数组每个数组取一个数让总和为 0还能不能做答案是可以而且框架几乎不用变折半枚举 哈希表。把 K 个数组分成两半一半大小 p另一半 K-p。先枚举前一半所有组合的和以及出现次数存入哈希表再枚举另一半所有组合查询互补值。复杂度是O(n^p n^(K-p))。想让总量最小应该让 p 和 K-p 尽量接近。于是有个漂亮的规律K3 时最优是 12复杂度 O(n^2)K4 时最优是 22复杂度 O(n^2)K5 时最优是 23复杂度 O(n^3)K6 时最优是 33复杂度 O(n^3)。一般地折半分组的复杂度大约在 O(n^ceil(K/2))。面试时如果能从四数相加推导到 K 数相加面试官通常眼睛会亮一下。这不是什么高深理论就是“分治思想在枚举问题里的迁移”。5.2 什么时候 22 不是最优解任何算法都有适用边界22 也一样。内存敏感时n 很大n^2 的表放不进内存就得退回 31拿时间换空间。值域很小时如果nums1 nums2的和只落在很小的整数区间可以直接用数组代替哈希表用“值 偏移量”做下标O(1) 访问且无哈希冲突。数据分布极端时比如某个数组只有一个元素最优分组就不再是平均分而是把特殊数组单独放一侧。这些属于进阶话题但面试时主动说出来会让你的回答从“背模板”升级成“有工程判断力”。5.3 现实工程里的对应场景有人觉得这类题只有面试用我不同意。举两个我实际遇到过的例子。第一个是数据报表里的交叉统计两张表按两个维度 join 之后做计数本质就是“先聚合一侧的组合再查另一侧的组合”。如果你直接四层循环暴力匹配数据量稍微上来就卡死换成预聚合加索引查询量级直接从 O(n^4) 掉到 O(n^2)。这和四数相加Ⅱ的 22 思路完全是同一件事。第二个是推荐系统里的特征命中判断要判断“用户 商品 场景 时段”是否命中某个优惠条件四维枚举和先聚合再查询的差别就是这道题暴力解和哈希表解的差别。所以这道题的价值不在“会做一道题”而在“掌握拆半、预聚合、互补查询这一整套思想”。学一道题会一类题这才划算。6. 我实际提交中踩过的坑从 WA 到 AC 的完整排查记录6.1 坑一错把“计数表”当“查找表”我第一次写这题时误以为用列表存下所有nums1 nums2的和就够了查询时对列表做遍历统计。逻辑上没错结果提交直接 TLE。排查后问题很明显列表查找是 O(表长)表长是 n^2我每查一次就要遍历几万个元素总体又回到了 O(n^4)。把列表换成字典之后key 存和、value 存次数查找变成 O(1)同样的逻辑立刻 AC。这件事给我的教训是哈希表的价值不是“能存数据”而是“把查找降为 O(1)”。以后凡是遇到“统计出现次数”类问题第一反应就应该想到字典而不是列表。6.2 坑二被“去重”带偏把计数表写成了集合因为之前先做的是四数之和那道题的核心难点是去重我到了四数相加Ⅱ还带着惯性直接把哈希表建成了set只记录“这个和出现过”不记录次数。小数据测试看不出问题直到我构造了一个重复值用例nums1 [1, 1] nums2 [-1, -1] nums3 [0, 0] nums4 [0, 0]正确答案是2 × 2 × 2 × 2 16因为每个下标都独立构成组合。而我的去重版本只返回 1因为每个数组里的值都一样被 set 合并成一种了。这个测试用例完美区分了“去重”和“计数”。从那以后我每次写完这类题都会先用一个全是重复值的 n2 用例自测能拦住大部分方向性错误。6.3 坑三忽略全零场景类型差点爆掉第二次提交前我自测了很多随机数据都通过结果在讨论区看到一个测试用例直接愣住nums1 nums2 nums3 nums4 [0] * 200。这种情况下答案不是几十几百而是200^4 1.6e9。我们平台给的函数签名返回int在 C 里 1.6e9 还勉强在 int 范围内但如果 n 再大一点或者出题人把约束改成 n2000答案就是 1.6e13int 直接溢出成负数。从此我养成了一个习惯写任何计数类题目先问自己“答案最大值是多大”。这个习惯帮我避开了不少隐含的类型坑。6.4 排查思路写给同样会踩坑的读者如果你也在这道题上 WA按这个顺序排查命中率很高是不是把计数写成了去重构造重复值用例验证一下。是不是查询键的符号搞反了打印一下need和哈希表里的 key 对比看看。是不是建表方向错了比如你存的是nums1 nums3查的却是nums3 nums4组合关系就乱了。是不是边界条件爆了类型全零数组过一遍看答案量级是否匹配返回类型。这四条我都在四数相加Ⅱ上交过学费。每次卡住的时候别盯着代码发呆先反推出一个能让代码出错的用例然后按这个清单排除比盲目加 print 快得多。我个人现在的做题习惯是先写纯字典版本跑通再顺手用那个重复值用例做一次自测最后才提交。这套流程看起来麻烦但在面试时能帮你省下最宝贵的试错次数。