LeetCode 454: 4Sum II (Pair-Sum Hash Counting)
LeetCode 454Hash TableMeet-in-the-MiddleToday we solve LeetCode 454 - 4Sum II.
Source: https://leetcode.com/problems/4sum-ii/
English
Problem Summary
Given four integer arrays nums1, nums2, nums3, nums4 of length n, count tuples (i, j, k, l) such that:
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.
Key Insight
Split 4-sum into two 2-sum groups: (a + b) + (c + d) = 0. If we know frequencies of all a+b, then each c+d only needs -(c+d) lookup.
Brute Force and Limitations
Brute force checks all quadruples in O(n^4), which is too slow when n grows (up to 200 in this problem).
Optimal Algorithm Steps (Pair-Sum Hash)
1) Build a hash map countAB: for every a in nums1 and b in nums2, increment countAB[a+b].
2) Initialize answer ans = 0.
3) For each c in nums3 and d in nums4, add countAB[-(c+d)] to ans.
4) Return ans.
Complexity Analysis
Time: O(n^2).
Space: O(n^2) for hash map.
Common Pitfalls
- Using set instead of frequency map (loses multiplicity).
- Integer overflow concern in some languages (safe in Java int for constraints, but use long if constraints change).
- Forgetting that same sum may appear many times and must be accumulated.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.HashMap;
import java.util.Map;
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map countAB = new HashMap<>();
for (int a : nums1) {
for (int b : nums2) {
int sum = a + b;
countAB.put(sum, countAB.getOrDefault(sum, 0) + 1);
}
}
int ans = 0;
for (int c : nums3) {
for (int d : nums4) {
ans += countAB.getOrDefault(-(c + d), 0);
}
}
return ans;
}
} func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
countAB := make(map[int]int)
for _, a := range nums1 {
for _, b := range nums2 {
countAB[a+b]++
}
}
ans := 0
for _, c := range nums3 {
for _, d := range nums4 {
ans += countAB[-(c+d)]
}
}
return ans
}#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2,
vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> countAB;
for (int a : nums1) {
for (int b : nums2) {
countAB[a + b]++;
}
}
int ans = 0;
for (int c : nums3) {
for (int d : nums4) {
auto it = countAB.find(-(c + d));
if (it != countAB.end()) ans += it->second;
}
}
return ans;
}
};from collections import defaultdict
from typing import List
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
count_ab = defaultdict(int)
for a in nums1:
for b in nums2:
count_ab[a + b] += 1
ans = 0
for c in nums3:
for d in nums4:
ans += count_ab[-(c + d)]
return ans/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number[]} nums3
* @param {number[]} nums4
* @return {number}
*/
var fourSumCount = function(nums1, nums2, nums3, nums4) {
const countAB = new Map();
for (const a of nums1) {
for (const b of nums2) {
const sum = a + b;
countAB.set(sum, (countAB.get(sum) || 0) + 1);
}
}
let ans = 0;
for (const c of nums3) {
for (const d of nums4) {
ans += countAB.get(-(c + d)) || 0;
}
}
return ans;
};中文
题目概述
给定四个长度为 n 的整数数组 nums1、nums2、nums3、nums4，统计满足：
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 的四元组数量。
核心思路
把四数之和拆成两组二数之和：(a+b)+(c+d)=0。先统计所有 a+b 的出现次数，再对每个 c+d 查找其相反数。
暴力解法与不足
暴力法四重循环，时间复杂度 O(n^4)，在 n=200 时不可接受。
最优算法步骤（两两求和 + 哈希计数）
1）遍历 nums1 与 nums2，用哈希表记录每个和 a+b 的出现次数。
2）答案初始化为 0。
3）遍历 nums3 与 nums4，将 countAB[-(c+d)] 累加到答案。
4）返回最终答案。
复杂度分析
时间复杂度：O(n^2)。
空间复杂度：O(n^2)。
常见陷阱
- 用 set 而不是频次 map，导致重复组合被漏算。
- 忘记同一个和可能出现多次，需要累计计数。
- 直接写四层循环会超时。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.HashMap;
import java.util.Map;
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map countAB = new HashMap<>();
for (int a : nums1) {
for (int b : nums2) {
int sum = a + b;
countAB.put(sum, countAB.getOrDefault(sum, 0) + 1);
}
}
int ans = 0;
for (int c : nums3) {
for (int d : nums4) {
ans += countAB.getOrDefault(-(c + d), 0);
}
}
return ans;
}
} func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
countAB := make(map[int]int)
for _, a := range nums1 {
for _, b := range nums2 {
countAB[a+b]++
}
}
ans := 0
for _, c := range nums3 {
for _, d := range nums4 {
ans += countAB[-(c+d)]
}
}
return ans
}#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2,
vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> countAB;
for (int a : nums1) {
for (int b : nums2) {
countAB[a + b]++;
}
}
int ans = 0;
for (int c : nums3) {
for (int d : nums4) {
auto it = countAB.find(-(c + d));
if (it != countAB.end()) ans += it->second;
}
}
return ans;
}
};from collections import defaultdict
from typing import List
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
count_ab = defaultdict(int)
for a in nums1:
for b in nums2:
count_ab[a + b] += 1
ans = 0
for c in nums3:
for d in nums4:
ans += count_ab[-(c + d)]
return ans/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number[]} nums3
* @param {number[]} nums4
* @return {number}
*/
var fourSumCount = function(nums1, nums2, nums3, nums4) {
const countAB = new Map();
for (const a of nums1) {
for (const b of nums2) {
const sum = a + b;
countAB.set(sum, (countAB.get(sum) || 0) + 1);
}
}
let ans = 0;
for (const c of nums3) {
for (const d of nums4) {
ans += countAB.get(-(c + d)) || 0;
}
}
return ans;
};
Comments