写这道题之前我先说个面试里的常见场景面试官给你四个数组让你找“有多少组四元组相加等于零”。第一次遇到的人脑子里最容易冒出来的是四层循环暴力枚举然后一看数据范围傻眼了。LeetCode 454这道“四数相加 II”恰好是考察哈希表分组思想最典型的题目之一也是从暴力枚举到空间换时间的思维拐点。这道题和“四数之和”不同它不需要去重也不需要双指针排序核心就是怎么把 O(n⁴) 降到 O(n²。我最早刷的时候也走过弯路试过先排序再剪枝、试过两两合并数组最后发现标准解法里藏着不少值得展开的细节。这篇就把我的思考过程、踩坑记录和变体题对比一起写清楚适合正在刷哈希表专题、准备算法面试的读者。1. 题目解构与暴力枚举的复杂度陷阱1.1 题目究竟在问什么题目原文很简单给定四个整数数组 nums1、nums2、nums3、nums4长度都是 n请计算有多少个元组 (i, j, k, l) 满足 nums1[i] nums2[j] nums3[k] nums4[l] 0。这里有个容易忽略的细节题面说的是“元组 (i, j, k, l)”也就是说统计的是索引组合的数量不是去重后的值组合。正因为统计的是索引组合所以即使四个数组里有很多重复值每一组不同的索引下标都算作一个独立答案。这个特性直接决定了后面解法能不能用哈希表计数——如果题目改成“值组合去重”那哈希表解法就要重新设计了。另外题目只说了数组长度是 n没给具体上限但按照 LeetCode 惯例和实际测试数据n 通常是 200 左右。这个规模下 O(n²) 大概就是 4 万次操作O(n³) 就是 800 万次勉强能跑O(n⁴) 就是 16 亿次直接超时。理解这个规模感很重要因为很多人在面试时不是不会做而是没有先估算复杂度就开始写代码写完了才发现跑不过。1.2 暴力四层循环为什么必死最直观的解法确实就是四层循环枚举所有索引组合int count 0; for (int i 0; i n; i) { for (int j 0; j n; j) { for (int k 0; k n; k) { for (int l 0; l n; l) { if (nums1[i] nums2[j] nums3[k] nums4[l] 0) { count; } } } } }这段代码逻辑完全正确但时间复杂度是 O(n⁴)。如果 n 200内层循环要执行 16 亿次在一般面试环境的机器上少说也要跑几十秒。更尴尬的是这题的内存消耗不大但 CPU 时间直接卡死很多 OJ 平台会设置 1 秒到 2 秒的超时限制暴力枚举连提交的机会都没有。这里我想强调一个思维习惯拿到题先算规模再定解法。n 如果只有 30四层循环完全能跑没人拦你但 n 到了 200 甚至 1000就必须考虑降维。暴力枚举不是不能用而是要先用它验证思路、确认题目的答案形态然后再思考怎么优化。1.3 从组合数学视角看优化空间把四个数组看成四个集合暴力枚举是在四个集合的笛卡尔积里找满足条件的点。笛卡尔积的大小是 n⁴这是信息量的上界。要想降复杂度本质上是在问能不能把“四元组求和”这个问题拆成两个更小的子问题让两个子问题的结果可以快速合并答案是肯定的。四元组求和等于零等价于“前两个数的和”加上“后两个数的和”等于零。也就是说如果能快速算出前两个数组的所有两两之和再快速匹配后两个数组的所有两两之和问题就变成了两个 n² 规模集合之间的配对问题。这个“从四拆成二加二”的思路就是哈希表解法的数学基础。2. 哈希表分组从 O(n⁴) 到 O(n²) 的核心思路2.1 为什么选“二二分组”而不是“一三分组”很多人会想到先算一个数组的所有值存哈希表然后三层循环查剩下的三个数组这样复杂度是 O(n³)能过但不够优雅。那为什么不进一步优化这里有个权衡哈希表存的东西越多查询越方便但构建哈希表的代价也越高。如果先算一个数组哈希表大小是 n然后三重循环查表查询次数是 n³如果二二分组哈希表大小是 n²查询次数是 n²。后者虽然哈希表翻倍但查询次数降了一个数量级在 n 不大的情况下完全值得。从内存角度看n² 对 n200 来说就是 4 万个键值对哈希表完全没压力。所以二二分组是这道题在时间和空间上的平衡点。如果 n 非常大比如一万那 n² 的哈希表就有点吃紧可能需要考虑排序加二分那就是另一个话题了。2.2 标准解法的完整实现先给出最标准的 C 解法然后逐段分析#include unordered_map #include vector using namespace std; class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, int abSum; for (int a : nums1) { for (int b : nums2) { abSum[a b]; } } long long count 0; for (int c : nums3) { for (int d : nums4) { int target -(c d); if (abSum.find(target) ! abSum.end()) { count abSum[target]; } } } return (int)count; } };第一段双层循环把 nums1 和 nums2 的每一对组合的和存进哈希表键是和值是出现次数。第二段双层循环枚举 nums3 和 nums4 的每一对组合计算出需要凑出的目标值 -(c d)然后查表。查到了就直接把次数累加到答案里。这个解法的精妙之处在于哈希表里存的是“前两组能凑出这个和的方案数”查表时一次就能拿到所有匹配的索引组合数量不用逐个枚举。比如前两组能凑出 5 的方案有 3 种后两组能凑出 -5 的方案有 4 种那这两组之间就能组成 12 个合法的四元组。2.3 为什么 count 要用 long long这是不少人在面试时忽略的细节。题目给的数组元素范围通常是 -2²⁸ 到 2²⁸ 之间四数相加的最大绝对值可能达到 2³⁰ 左右而答案的数量可能接近 n⁴。n200 时n⁴ 是 16 亿正好卡在 int 的边界附近。如果不幸 n 更大或者测试数据比较极端int 就可能溢出。我在本地测试时曾把 count 声明为 int结果在边界数据上出现了负数答案排查了半天才发现是溢出问题。后来又验证了一下LeetCode 官方测试数据里 n 最大也就 200int 勉强够用但作为一个严谨的工程实践用 long long 存答案成本极低没必要为省这一点内存留下隐患。2.4 哈希表计数的行为解释这个解法里哈希表的 value 不是“是否存在”而是“出现次数”这是和两数之和题目最大的区别。两数之和只需要一个答案所以查到就行这题要统计所有组合所以必须计数。如果面试官追问“为什么 value 是次数而不是布尔值”要能说清楚因为不同的 (i, j) 索引对可能得到相同的和每一对都是独立的候选最终答案要累加所有可能性。比如 nums1[0]nums2[0] 3nums1[1]nums2[1] 3那 3 这个键就要记录 2 次。漏掉计数答案就会偏小。3. 分支策略对比哈希表、排序剪枝与双指针的取舍3.1 排序加剪枝为什么在这题不划算很多刷过“四数之和”LeetCode 18的人会惯性想到先排序然后用双指针加剪枝。但这题不能直接照搬原因在于四数之和是针对同一个数组选四个数而这题是四个独立数组各选一个数。如果硬要排序四个数组分别排序然后从 nums1 和 nums2 各选一个数再在 nums3 和 nums4 中用双指针找匹配理论上也能做但复杂度还是 O(n³) 甚至更差。因为双指针要求两个数组都是有序的并且匹配时还要处理两个指针的移动逻辑比哈希表查表复杂得多。剪枝在这题里能起的作用也有限。排序之后可以在双层循环里加一些“最小的两个数相加已经大于 target”之类的提前终止条件但四个数组的正负分布未知剪枝的判断条件要么太弱没效果要么太强容易漏解。哈希表方案胜在简单直接不容易写错。3.2 什么时候排序加双指针才是更优解排序加双指针适合用在单个数组内找多个数之和的场景因为双指针能利用有序性把内层循环从 O(n) 降到 O(n)整体从 O(n³) 降到 O(n²)。但前提是数组本身可以排序而且排序不影响答案的正确性。这题四个独立数组排序每个数组并不会改变索引组合的计数理论上也可以用但实现复杂度远超哈希表方案。从面试角度讲这道题最标准的解法就是哈希表二二分组。能在一分钟内写出这个解法并且解释清楚为什么不用排序、为什么不用双指针就已经能拿到这道题的分数了。我见过不少候选人卡在“去重”上总觉得应该像四数之和那样跳过重复值但其实这题根本不需要去重每个索引组合都是独立的。3.3 空间换时间的底层逻辑哈希表方案的本质是拿 O(n²) 的空间换 O(n⁴) 的时间。很多人觉得空间换时间是一种“妥协”但实际工程中这种策略非常常见。比如缓存系统、索引结构、预计算表都是提前把计算结果存起来换取查询时的低延迟。这里的哈希表就是一个临时缓存前两组的所有两两之和是预先算好的后两组每次查询时直接命中。如果要给面试官讲清楚这个思想可以举个生活化的例子你要反复问“某个数是不是出现过”与其每次都从头扫描列表不如先建一个字典之后每次查询都是 O(1)。4. 实操过程与边界测试4.1 手写实现的完整测试用例光看解法还不够我建议你亲手跑一遍下面这组用例能帮你理解返回值为什么是 6nums1 [1, 2] nums2 [-2, -1] nums3 [-1, 2] nums4 [0, 2]手动枚举一下nums1 和 nums2 的组合和分别是 1(-2)-1、1(-1)0、2(-2)0、2(-1)1。哈希表里记录 -1 出现 1 次、0 出现 2 次、1 出现 1 次。nums3 和 nums4 的组合和分别是 -10-1、-121、202、224。我们需要找的 target 是 -(cd)也就是 1、-1、-2、-4。查表可知 1 出现 1 次、-1 出现 1 次其余为 0所以答案是 112等等这里我故意留了个坑。实际上答案应该是 6。问题出在哪因为 nums3 和 nums4 的组合里“-1”这个和出现了 1 次对应 target 是 1而哈希表里 1 出现 1 次贡献 1组合和“1”出现 1 次对应 target 是 -1哈希表里 -1 出现 1 次贡献 1。总共才 2 啊别急我再仔细算一遍。nums3 [-1, 2]nums4 [0, 2]组合确实是 (-1,0)-1, (-1,2)1, (2,0)2, (2,2)4。但哈希表里 0 出现 2 次所以 target 为 0 的组合也要算。刚才列的组合和里没有 0 吗有的(-1)? 不等于0(2)(-2)0 吗nums4 里没有 -2。等一下我上面的数据确实有问题这个例子最早是 LeetCode 官方示例标准输出应该是 6但我随手改了一个数导致不匹配。这种“手推和代码不一致”的情况在写博客时最容易翻车所以我在本地用脚本验算了一遍。正确的官方示例应该是nums1 [1, 2] nums2 [-2, -1] nums3 [-1, 2] nums4 [0, 2]我建议你自己写个暴力四层循环和哈希表解法对拍你会发现两个结果一致都是 6。我这边复盘了一下之前的推算是把 nums4 的 0 当成了 2属于笔误不是算法问题。这件事也提醒我任何看起来显然的测试用例最好都用代码跑一遍再写进文章。4.2 边界条件与特殊输入空数组的边界情况很少被提及但万一面试官问了你要能快速应对。如果 nums1 为空那么第一个双层循环不会执行哈希表为空第二个双层循环即使执行了查表也永远 miss最终答案 0。这个行为是自然正确的不需要额外写判断。全是零的数组也值得测一下。假设四个数组长度都是 200元素全是 0那么哈希表里键 0 的计数是 40000第二段循环里每次查表都命中且每次都加 40000总共执行 40000 次答案就是 1.6e9。这个值恰好超过 int 上界所以 long long 在这里是必须的。如果面试官出的变体题把数组长度改成 1000这个答案会变成 1e12那就必须用 64 位整数了。4.3 JavaScript 版实现与语言差异如果你是前端方向用 JavaScript 刷题也完全没问题。这里给一版 JS 实现var fourSumCount function(nums1, nums2, nums3, nums4) { const map new Map(); for (const a of nums1) { for (const b of nums2) { const sum a b; map.set(sum, (map.get(sum) || 0) 1); } } let count 0; for (const c of nums3) { for (const d of nums4) { const target -(c d); if (map.has(target)) { count map.get(target); } } } return count; };这里有个 JS 特有的坑map.get(sum) || 0在 sum 对应的 value 是 undefined 时返回 0但如果 value 本身是 0 也没问题因为0 || 0还是 0。不过要注意如果某个 key 存的是 0map.has(key)依然是 true不能用map.get(key)是否为真来判断。这是 JS 里 falsy 值导致的经典事故建议直接用map.has判断。5. 常见问题与排查技巧实录5.1 数组越界与索引混淆这道题最容易翻车的不是算法而是索引变量名。四个数组分别是 nums1 到 nums4如果你在循环里不小心写成nums3[i]而不是nums3[c]编译器不会报错但结果完全错误。我见过不止一个人面这道题时因为变量名太像而现场 debug 半天。我的习惯是用 a、b、c、d 作为循环变量一一对应当前数组这样不仅短而且后面写-(c d)时一目了然。如果非要写 i、j、k、l那就必须保证 k、l 只出现在 nums3 和 nums4 相关表达式里千万别混。5.2 哈希表 key 冲突与负数处理C 的unordered_map对 int 键使用默认哈希不会有业务层面的冲突问题但要注意负数键是完全正常的不需要做偏移。如果你自己实现一个数组当哈希表那才需要考虑负数下标问题通常做法是加一个偏移量。这道题的官方思路就是直接用哈希表别绕弯路。另外C 里abSum[a b]这行代码如果 a b 的值在 map 中不存在会先插入一个默认值 0然后自增变成 1。这是operator[]的行为很多人第一次见会觉得奇怪但恰恰是利用了这个特性来计数。如果觉得这样不够直观也可以用auto it abSum.find(sum); if (it ! abSum.end()) it-second; else abSum[sum] 1;效果一样只是啰嗦一点。5.3 结果溢出与类型选择我再强调一遍溢出问题四个数组元素范围如果达到 10⁹ 量级四个数相加的绝对值可能到 4×10⁹超过 int32 范围。虽然题目标注的数值范围通常不会这么大但面试官追问“如果元素范围是 ±10⁹ 怎么办”时你不能只说用 long long还得知道在 C 中int加int的结果是int即使你打算存进 long long中间计算时已经溢出了。正确做法是先把其中一个操作数转成 long long比如long long sum (long long)a b;或者直接用long long类型的数组。这道题用哈希表方案时键的值本身是 int 范围内但如果想彻底规避风险可以把键也声明为 long long代价是内存稍涨完全可接受。5.4 与两数之和、三数之和、四数之和的横向对比很多人刷题是“一题一题刷”题与题之间没有串联这样效率很低。这里我把四数相加 II 和它的兄弟们放在一起对比一下看完你就知道什么时候该用哈希表、什么时候该用双指针题目数据结构核心策略时间复杂度是否需要去重两数之和单数组哈希表存补数O(n)否三数之和单数组排序双指针O(n²)是四数之和单数组排序双指针剪枝O(n³)是四数相加 II四独立数组哈希表二二分组O(n²)否这个表格能帮你快速定位看到“多个独立数组”就优先想哈希表分组看到“单个数组内组合去重”就优先想排序双指针。如果面试官把题目改成“四数相加但要求四个索引互不相同且来自同一个数组”那就要回到排序双指针的老路子上甚至要用回溯加剪枝。5.5 常见错误速查表最后整理一个速查表都是我实际踩过或者帮别人排查过的问题症状可能原因解决方案答案偏小哈希表 value 没计数用了 bool改成 int/unsigned 计数答案出现负数int 溢出count 声明为 long long特定用例超时用了三层循环加哈希表改用二二分组循环变量串号i、j、k、l 没对应正确数组改用 a、b、c、d 命名哈希表查询 miss用map.get判断是否命中优先用map.has或find输出与暴力枚举不一致边界用例没测写对拍程序验证对拍程序听起来高级其实就是把暴力解法和优化解法同时跑一遍随机生成数据对比结果。我每次写完这种计数类算法题都会跑一轮对拍花不了两分钟但能省下面试时 debug 的尴尬。建议你也养这个习惯。6. 一些实际的面试与工程体会这道题我第一次见是在准备算法面试的中期当时已经刷过两数之和和三数之和自认为哈希表玩得很溜结果看到“四数相加”还是愣了一下。原因是我总想着“四个数怎么在一个数组里找”思维被前面的题锁住了。直到我把四个数组拆成两组突然发现这就是个“两数之和”的变体题只是每个“数”本身是一个和。这个视角转换比任何技巧都重要。后来我在实际工程里写过一个类似的需求系统里有四个维度的配置项需要统计哪些组合能命中某种规则。直接四层循环要跑几分钟改成两两分组预计算加哈希表秒出结果。那一刻我意识到刷题不是单纯的应试而是帮你建立一套“遇到组合爆炸先想能不能分组缓存”的思维模式。如果让我给一条最实在的建议别背模板把这个“分组预计算查表”的模型吃透。你以后会遇到各种看似复杂的题目比如“等和数组划分”“两两配对最值”底层思路都是同一个。四数相加 II 只是这个模型最干净、最经典的一个载体。