4Sum II

Problem Id: 454 Difficulty: Medium


Intuition

Solution


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
        """
        pos = {}
        neg = {}
        for i in A:
            for j in B:
                key = i + j
                if key not in pos:
                    pos[key] = 1
                else:
                    pos[key] += 1
        for i in C:
            for j in D:
                key = i + j
                if key not in neg:
                    neg[key] = 1
                else:
                    neg[key] += 1

        ans = 0
        for key in pos.keys():
            if -key in neg:
                ans += pos[key] * neg[-key]
        return ans