454. 4Sum II

solution454.py

# https://leetcode.com/problems/4sum-ii/description/
class Solution(object):
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        # if A[a] + B[b] + C[c] + D[d] = 0, then A[a] + B[b] == -C[c] - D[d]
        sum_dict = {}
        for a in A:
            for b in B:
                left_side = a + b
                if left_side in sum_dict:
                    sum_dict[left_side] += 1
                else:
                    sum_dict[left_side] = 1
        count = 0
        for c in C:
            for d in D:
                right_side = -c - d
                if right_side in sum_dict:
                    count += sum_dict[right_side]
        
        return count