四数相加 II 为什么用哈希表拆成两半？

简化版

四数相加 II 要统计 a+b+c+d=0 的组合数。把四个数组拆成两组，先枚举 A+B 的所有和并用哈希表计数，再枚举 C+D，查 -(c+d) 出现次数。复杂度从 O(n⁴) 降到 O(n²)，空间 O(n²)。

详细版

两两拆分的本质是“空间换时间”。A、B 的所有 pair sum 有 n² 个，用 Map<sum, count> 存起来；C、D 每得到一个和 s，能配成 0 的数量就是 map.get(-s)。

int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> ab = new HashMap<>();
    for (int a : A) {
        for (int b : B) {
            ab.put(a + b, ab.getOrDefault(a + b, 0) + 1);
        }
    }
    int ans = 0;
    for (int c : C) {
        for (int d : D) {
            ans += ab.getOrDefault(-(c + d), 0);
        }
    }
    return ans;
}

哈希表必须存次数，因为不同 (a,b) 可能产生相同的和。

完整版教学

一、暴力为什么不可接受

四个长度为 n 的数组，暴力枚举四元组需要 n⁴ 次。若 n=500，n⁴ 是 625 亿级，显然太慢。题目只要求统计个数，不要求列出组合，这给了我们聚合中间结果的机会。

把 a+b+c+d=0 改写成 a+b = -(c+d)，四数问题就变成两个两数和的匹配问题。

二、为什么拆成两半最合适

如果只枚举一个数组，剩下三个数组仍然是 O(n³)。拆成两半后，每半都是 n² 个和，构建和查询都是 n² 量级，复杂度降到 O(n²)。

A+B 所有和: n² 个
C+D 所有和: n² 个
匹配方式: 哈希查补数

这是典型的 meet-in-the-middle 思路，也就是“中间相遇”。

三、哈希表为什么存 sum 到次数

不同 pair 可能有相同的和，它们都能和另一半的补数配对。例如 A+B 中和为 1 出现 3 次，C+D 中和为 -1 出现 2 次，则贡献 3*2=6 个四元组。

A+B 和	次数
1	3
0	1
-2	4

所以 map 的 value 必须是 count，而不是只存存在性。

四、手算一个例子

设 A=[1,2]，B=[-2,-1]，C=[-1,2]，D=[0,2]。

A+B: -1(1次), 0(2次), 1(1次)
C+D:
  -1+0=-1 -> 查 1，有 1 次
  -1+2=1  -> 查 -1，有 1 次
  2+0=2   -> 查 -2，无
  2+2=4   -> 查 -4，无
答案 2

这个例子能说明“查补数”和“次数累加”两个关键点。

五、复杂度与溢出边界

构建 A+B 需要 n² 次，扫描 C+D 也需要 n² 次，所以时间 O(n²)。哈希表最多存 n² 种不同和，空间 O(n²)。如果数值范围大，a+b 或 c+d 可能溢出 int，工程中可用 long 作为 key。

面试要明确这是用空间换时间；如果 n 很大导致 n² 内存不可接受，就要讨论近似、分块或外部排序等工程策略。

六、常见误区与追问

记忆钩子：四数别硬选四层循环，先把左半边所有可能性压成“和的频次表”。

误区：Map 只存 sum 是否存在。 题目统计组合数，相同 sum 的多个 pair 都要计入。
误区：拆成 A+B+C 和 D。 这样仍然需要 O(n³) 构建，不能达到目标。
误区：把四数之和 I 的去重逻辑搬过来。 本题是四个数组统计下标组合，不需要去重结果列表。
追问：为什么答案可能超过 int？ 组合数最多可到 n⁴ 级，严格场景可用 long 保存答案。
追问：能否先存 C+D 再查 A+B？ 可以，完全对称。
追问：这类思想还能用在哪？ k-sum 计数、折半搜索、子集和等问题都常用拆半。

七、加强记忆

四数相加 II 的固定套路是：四层循环太大，拆成两个两层循环；左边建 sum -> count，右边查 -sum 并累加次数。看到“多个数组求组合计数”，先想能否拆半并用哈希表合并中间状态。

简化版

详细版