454. 四数相加 II
题目描述
输入四个整数数组 nums1、nums2、nums3、nums4，它们的长度都是 n。
从每个数组中各取一个下标，组成四元组 (i, j, k, l)，其中每个下标都在 0 到 n - 1 之间。
统计有多少个这样的四元组，使选出的四个元素之和恰好为 0，返回这个数量。
示例 1
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] 输出：2
解释：(0,0,0,1) 得 1 - 2 - 1 + 2 = 0，(1,1,0,0) 得 2 - 1 - 1 + 0 = 0，共 2 组。
示例 2
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] 输出：1
解释：唯一的四元组 (0,0,0,0) 和为 0。
数据范围
n == nums1.length == nums2.length == nums3.length == nums4.length1 <= n <= 200-2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28
解题思路
暴力枚举四重循环是 O(n^4)。把四个数组分成两组：先枚举 nums1、nums2 的所有和 a+b，用哈希表记录每个和出现的次数；再枚举 nums3、nums4 的 c+d，需要的配对是 a+b = -(c+d)，直接查表把次数加到答案。这是“两数之和”的分组版本。
为什么正确
cnt[s] 等于满足 nums1[i] + nums2[j] = s 的 (i, j) 个数；处理完若干 (c, d) 后，ans 等于这些 (c, d) 各自能配成和为 0 的 (i, j) 个数之和。
复杂度分析
时间 O(n^2)，空间 O(n^2)（哈希表最多 n^2 个键）。
易错点
哈希表里要存“出现次数”而不是“是否出现”：同一个和可能由多对 (i, j) 得到，每一对都算一个独立的元组。另外题目统计的是下标元组，不需要去重。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
cnt = {}
for a in nums1:
for b in nums2:
cnt[a + b] = cnt.get(a + b, 0) + 1
ans = 0
for c in nums3:
for d in nums4:
ans += cnt.get(-c - d, 0)
return ansclass Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int a : nums1) {
for (int b : nums2) {
cnt.put(a + b, cnt.getOrDefault(a + b, 0) + 1);
}
}
int ans = 0;
for (int c : nums3) {
for (int d : nums4) {
ans += cnt.getOrDefault(-c - d, 0);
}
}
return ans;
}
}class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> cnt;
for (int a : nums1) {
for (int b : nums2) {
cnt[a + b]++;
}
}
int ans = 0;
for (int c : nums3) {
for (int d : nums4) {
auto it = cnt.find(-c - d);
if (it != cnt.end()) ans += it->second;
}
}
return ans;
}
};func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
cnt := map[int]int{}
for _, a := range nums1 {
for _, b := range nums2 {
cnt[a+b]++
}
}
ans := 0
for _, c := range nums3 {
for _, d := range nums4 {
ans += cnt[-c-d]
}
}
return ans
}var fourSumCount = function(nums1, nums2, nums3, nums4) {
const cnt = new Map();
for (const a of nums1) {
for (const b of nums2) {
cnt.set(a + b, (cnt.get(a + b) || 0) + 1);
}
}
let ans = 0;
for (const c of nums3) {
for (const d of nums4) {
ans += cnt.get(-c - d) || 0;
}
}
return ans;
};function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
const cnt = new Map<number, number>();
for (const a of nums1) {
for (const b of nums2) {
cnt.set(a + b, (cnt.get(a + b) || 0) + 1);
}
}
let ans = 0;
for (const c of nums3) {
for (const d of nums4) {
ans += cnt.get(-c - d) || 0;
}
}
return ans;
}