254. 4Sum II

Split the four arrays into two halves. Count every pairwise sum from the first two arrays in a hash map, then for each pairwise sum of the last two arrays look up how many first-half sums cancel it (equal its negative). This turns an O(n^4) search into O(n^2).

Split 4 into 2 + 2

A brute force over all (i, j, k, l) is O(n^4). Instead split the problem in half.

Step 1 — tally the left half. Build a hash map count where count[a+b] is how many pairs (i, j) give nums1[i] + nums2[j] = a+b.

Step 2 — cancel with the right half. For each pair (k, l) with sum c + d = nums3[k] + nums4[l], we need a + b + c + d = 0, i.e. a + b = -(c + d). Add count[-(c+d)] to the answer.

count = {}
for a in nums1:
    for b in nums2: count[a+b] += 1
ans = 0
for c in nums3:
    for d in nums4: ans += count.get(-(c+d), 0)
return ans

Worked example

nums1=[1,2], nums2=[-2,-1], nums3=[-1,2], nums4=[0,2].

Left-half sums: 1+(-2)=-1, 1+(-1)=0, 2+(-2)=0, 2+(-1)=1 → count = {-1:1, 0:2, 1:1}.

Right-half sums and lookups of the negation:

• -1+0=-1 → need 1 → count[1]=1
• -1+2=1 → need -1 → count[-1]=1
• 2+0=2 → need -2 → 0
• 2+2=4 → need -4 → 0

Total = 1 + 1 = 2.

Complexity

• Time: O(n^2).
• Space: O(n^2) for the hash map.

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int a : nums1) {
            for (int b : nums2) {
                count.merge(a + b, 1, Integer::sum);
            }
        }
        int ans = 0;
        for (int c : nums3) {
            for (int d : nums4) {
                ans += count.getOrDefault(-(c + d), 0);
            }
        }
        return ans;
    }
}