454. 4Sum II

class Solution:
    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
        """
        '''
        本题是纸老虎，原本找四元组暴力解法时间复杂度理应为O(n^4)，
        但是，题目给出N <= 500，所以可以使用O(n^2)解题。
        这里有个小技巧，当题目给出数据集大小时，可以依据经验快速选用某些看起来高复杂度的算法
        本题还有一处需要注意的地方：
        如何正确统计四元组数目？
        1、为了达到O(n^2)的复杂度，需要两两组合元素，即要求记录每一二元组的频数
        2、由于题目给出元素大小和均在整数范围内，所以使用字典是方便的
        3、注意并体会本题的键值对应
        '''
        assert A is not None or B is not None or C is not None or D is not None
        dict_1 = {}
        for idx_c, c in enumerate(C):
            for idx_d, d in enumerate(D):
                if -(c + d) in dict_1:
                    dict_1[-(c + d)] += 1
                else:
                    dict_1[-(c + d)] = 1
        res = 0
        for a in A:
            for b in B:
                if a + b in dict_1:
                    res += dict_1[a + b]
        return res