4Sum II
Medium · Arrays & Hashing · Explanation and code example
Hash Pair Sums
How it works
Split the four-array sum into two pair sums. Count how often each sum from the first two arrays appears. For each pair from the other two arrays, look up the frequency of its negated sum to count every zero-sum index tuple.
Steps
- Count every nums1 + nums2 pair sum.
- Enumerate nums3 + nums4 pair sums.
- Add the stored frequency of the opposite sum.
Complexity
- Time: O(n²) expected for four arrays of length n.
- Space: O(n²).
Things to watch for
- Store frequencies, rather than a set, because repeated values create multiple index tuples.
- Each array contributes one index.
- The lookup sum must be negated.
Python code example
import collections
class Solution:
def fourSumCount(self, nums1: list[int], nums2: list[int],
nums3: list[int], nums4: list[int]) -> int:
count = collections.Counter(a + b for a in nums1 for b in nums2)
return sum(count[-c - d] for c in nums3 for d in nums4)
C++ code example
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3,
vector<int>& nums4) {
int ans = 0;
unordered_map<int, int> count;
for (const int a : nums1)
for (const int b : nums2)
++count[a + b];
for (const int c : nums3)
for (const int d : nums4)
if (const auto it = count.find(-c - d); it != count.cend())
ans += it->second;
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.