https://leetcode.com/problems/4sum-ii

Let us look at pairs of numbers from A and B and calculate all O(n^2) of them. Next, we look at all pairs from C and D and again calculate all of them. Now, our problem is reduced to 2-sum problem: we need to find two numbers from two lists, such that sum of them equal to 0. There is couple of moments we need to care about:

  1. There can be duplicates, so we keep Counter() for our sums.
  2. When we update ans, we check how many numbers we have in first counter and multiply it by how many times we have for opposite number.

Complexity: total complexity is O(n^2) to look at all pairs from (A, B) and (C, D). Space complexity is also O(n^2). One possible optimization is to first create counters from our lists and work with them directly.

class Solution:
    def fourSumCount(self, A, B, C, D):
        Cnt1, Cnt2, ans = Counter(), Counter(), 0
        for a, b in product(A, B):
            Cnt1[a + b] += 1
            
        for c, d in product(C, D):
            Cnt2[c + d] += 1
            
        for val in Cnt1:
            if -val in Cnt2:
                ans += Cnt1[val]*Cnt2[-val]
                
        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 0454