题目描述
给你四个整数数组 nums1、nums2、nums3 和 nums4，数组长度都为 n，请你计算有多少个元组 (i, j, k, l)，满足：
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0。
思路分析
暴力做法是四重循环，时间复杂度 O(n^4)，会直接超时。
这题的关键是把四数问题拆成两组两数问题：
- 先遍历
nums1和nums2，统计所有a + b的出现次数，存入哈希表。 - 再遍历
nums3和nums4，设当前和为c + d。 - 如果想让总和为
0，就需要a + b = -(c + d)。 - 只要
-(c + d)在哈希表里出现过，就把对应次数累加到答案里。
这样可以把复杂度从 O(n^4) 降到 O(n^2)。
C++ 代码实现
class Solution {
public:
int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3,
vector<int> &nums4) {
unordered_map<int, int> umap;
int count = 0;
for (int a : nums1) {
for (int b : nums2) {
umap[a + b]++;
}
}
for (int c : nums3) {
for (int d : nums4) {
auto iter = umap.find(-(c + d));
if (iter != umap.end()) {
count += iter->second;
}
}
}
return count;
}
};复杂度分析
- 时间复杂度：
O(n^2)，两次双重循环。 - 空间复杂度：
O(n^2)，最坏情况下哈希表需要存储n^2个两数和。
易错点记录
- 误写成
umap[c + d]，正确是去查-(c + d)。 - 忘记哈希表存的是“出现次数”，不是只存是否出现。
- 结果累加时写成
count++，应当是count += umap[目标值]。
总结
这题是哈希表降维打击的经典题型。把四数求和拆成两次两数求和，再用哈希表做频次统计，复杂度就能从 O(n^4) 直接降到 O(n^2)。以后遇到 k 数之和计数问题，也可以优先想一想这种“分组 + 哈希”思路。
