四数相加 II python(leetcode454)

四数相加 II python(leetcode454)

#454. 四数相加 II

得到满足 A[i]+B[j]+C[k]+D[l]=0A[i]+B[j]+C[k]+D[l]=0 的四元组数目

将四个数组分成两部分，AA 和 BB 为一组，CC 和 DD 为另外一组

        # 分两步计算
        # 第一步计算nums1和nums2中相加的值，值作为key，每个值出现的次数作为value存入哈希表record
        # 第二步计算nums3和nums4中相加的值，计算-(nums3+nums4)，如果其在record中出现，则count统计出现的次数
        # 对于每个-(nums3+nums4)，都统计其在record中出现的次数
        # 数组的长度1 <= n <= 200

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type nums3: List[int]
        :type nums4: List[int]
        :rtype: int
        """
        # 分两步计算
        # 第一步计算nums1和nums2中相加的值，值作为key，每个值出现的次数作为value存入哈希表record
        # 第二步计算nums3和nums4中相加的值，计算-(nums3+nums4)，如果其在record中出现，则count统计出现的次数
        # 对于每个-(nums3+nums4)，都统计其在record中出现的次数
        # 数组的长度1 <= n <= 200
        record = {}
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                sum1 = nums1[i] + nums2[j]
                if sum1 in record:
                    record[sum1] += 1
                else:
                    record[sum1] = 1
        count = 0
        for k in range(len(nums3)):
            for l in range(len(nums4)):
                sum2 = -(nums3[k] + nums4[l])
                if sum2 in record:
                    count += record[sum2]  
        return count