4sum Ii - Leetcode Solution

The problem statement for 4Sum II on LeetCode is as follows:

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To solve this problem, we can use a hash table to store all possible sums of two arrays A and B. We can then iterate over all possible pairs of arrays C and D, and check how many pairs of sums from A and B add up to the negative of the current sum from C and D.

Here’s how we can implement this solution:

1. Initialize a hash table to store the counts of sums of pairs from A and B.

2. Loop through the lists A and B, and add all possible sums to the hash table with their count.

from collections import defaultdict

def fourSumCount(A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    sums = defaultdict(int)
    for a in A:
        for b in B:
            sums[a+b] += 1

3. Loop through the lists C and D, and for each pair (c,d), check how many pairs of sums from A and B add up to -(c+d).

    count = 0
    for c in C:
        for d in D:
            count += sums[-(c+d)]
            
    return count

Overall, the time complexity of this solution is O(n^2) because we are iterating through all possible pairs of arrays A, B, C, and D. However, the space complexity is also O(n^2) because we are storing all possible sums of pairs from A and B in a hash table.

1