LeetCode 454. 四数相加 II
目录
题目描述
题意分析
给定四个等长的整数数组，长度都是 $n$，要求统计有多少个下标四元组 $(i, j, k, l)$ 满足四个数组对应位置取出的数之和为 0。
这里最容易被忽略的一点是：统计对象是下标组合而不是数值组合。即使四个位置上的数值完全一样，只要下标不同就算作不同的方案，因此完全不需要去重，这和「三数之和」「四数之和」那类要求返回互不相同数值组合的题目有本质区别。
约束方面，$n$ 通常在几百的量级，$n^4$ 会达到上百亿次显然不可行，而 $n^2$ 只有十万级别，非常宽松。这个数量级差距本身就是提示：应当把四重枚举压成两重。另外每个元素的绝对值可以到 $2^{28}$ 量级，四个数相加最多约 $2^{30}$，仍在 32 位范围内，中间的两数之和更不会溢出；而答案上界是 $n^4$，在 $n$ 为几百时也仍在 32 位整数可表示范围内。
边界情形：四个数组允许包含重复值，也允许全为 0——此时任意四元组都成立，答案就是 $n^4$，任何依赖「值唯一」的做法都会在这里崩掉。
解法：两两分组哈希计数
核心思路
四重枚举需要 $O(n^4)$。由于四个下标彼此独立，可以把等式
\[a+b+c+d=0\]改写为
\[a+b=-(c+d)\]也就是左右两部分的和互为相反数。
先枚举前两个数组，用哈希表记录每个两数和出现了多少次；再枚举后两个数组，查询相反数的出现次数并累加。
哈希表必须存“次数”而不是“是否出现”。维护不变量：
sumCount[x]等于当前已枚举的(i,j)中满足nums1[i] + nums2[j] = x的下标对数量。对任意后半下标对
(k,l)，所有和为-(nums3[k] + nums4[l])的前半下标对都能与它唯一组成合法四元组；反之每个合法四元组也会在对应的后半下标对处被统计一次，因此不重不漏。
解题步骤
- 双重循环枚举
nums1和nums2，统计每个两数和的出现次数。- 双重循环枚举
nums3和nums4，计算当前和sum。- 将
sumCount[-sum]加入答案；查不到时贡献为 0。- 返回累计的下标四元组数量，不需要排序或去重。
样例中前两组和为 0 的下标对可能有多组。后两组需要和为 0 时，这些下标对都应计入，所以集合无法替代计数表。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> sumCount = new HashMap<>();
for (int a : nums1) {
for (int b : nums2) {
int sum = a + b;
sumCount.put(sum, sumCount.getOrDefault(sum, 0) + 1);
}
}
int ans = 0;
for (int c : nums3) {
for (int d : nums4) {
ans += sumCount.getOrDefault(-(c + d), 0);
}
}
return ans;
}
}
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
sumCount := make(map[int]int)
for _, a := range nums1 {
for _, b := range nums2 {
sumCount[a+b]++
}
}
ans := 0
for _, c := range nums3 {
for _, d := range nums4 {
ans += sumCount[-(c+d)]
}
}
return ans
}
复杂度分析
- 时间复杂度：平均 $O(n^2)$。建表和查询各进行 $n^2$ 次，哈希操作平均为 $O(1)$。
- 空间复杂度：$O(n^2)$。最坏情况下前两个数组的两数和都不同。
关键点总结
- 多组独立集合凑目标值时，优先尝试把等式拆成两半。
- 统计下标方案数要保存频次；只有判断存在性时才用集合。
- 两段双重循环是并列关系，复杂度相加而不是相乘。
- 本题无需去重，它与“返回唯一数值组合”的四数之和是不同问题。
易错点总结
- 哈希表只记录和是否存在：重复下标对会被少算。
- 查询
sumCount[c+d]：忘记取相反数，求成了两边和相等。- 对结果去重：题目统计的是下标四元组，不是不同的数值组合。
- 把建表放进后半双重循环：复杂度重新退化到 $O(n^4)$。
- 套用排序加双指针的“四数之和”：会混淆数组来源并丢失重复方案。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1. 两数之和 | 简单 | 只需找出一组下标，边遍历边查表 |
| 170. 两数之和 III - 数据结构设计 | 简单 | 把补数查询封装成支持动态添加的数据结构 |
| 18. 四数之和 | 中等 | 同一数组内取四个数并要求数值去重，需排序 |
| 15. 三数之和 | 中等 | 固定一个数后双指针，重点在跳过重复值 |
| 888. 公平的糖果交换 | 简单 | 由总和差推出目标差值，再单次查表 |
| 560. 和为 K 的子数组 | 中等 | 把前缀和差值转成补数计数，同样存次数 |