Count tuples (i,j,k,l) such that nums1[i]+nums2[j]+nums3[k]+nums4[l] == 0.
Input: nums1=[1,2], nums2=[-2,-1], nums3=[-1,2], nums4=[0,2] → Output: 2
Input: nums1=[0], nums2=[0], nums3=[0], nums4=[0] → Output: 1
Split into two pairs. Map sums of pair1, then look for negation in pair2.
- HashMap: store count of all a+b sums for nums1 and nums2
- For each c+d in nums3 and nums4
- Look up -(c+d) in map and add count to result
- Return result
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
for (int a : nums1)
for (int b : nums2)
map.merge(a + b, 1, Integer::sum);
int count = 0;
for (int c : nums3)
for (int d : nums4)
count += map.getOrDefault(-(c + d), 0);
return count;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)