四数相加2-哈希表

两数相加2-力扣

• 4个独立数组，A[i] + B[j] + C[k] + D[l] = 0，不用考虑有重复的4个元素相加等于0的情况
• python中，if i in dict，这里dict等价于dict.keys(),表示元素是否出现在字典的keys中
  -解题步骤：

1. 用dict做哈希表，key为a+b，value为a+b出现次数
2. 用count统计次数，遍历数组C和D，若0-(c+d)出现在hash_map中，取出dict中对应的value，加给count
3. 返回count

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        #用dic来做hash表，a+b作为key，a+b出现次数作为value
        hash_map=dict()        
        for a in nums1:
            for b in nums2:
                if (a+b) in hash_map:
                    hash_map[a+b]+=1
                else:
                    hash_map[a+b]=1
        
        #遍历C和D，若0-(c+d)出现在hash_map中，把对应的value取出，覆盖计数变量count
        count=0
        for c in nums3:
            for d in nums4:
                tmp=0-(c+d)
                if tmp in hash_map:
                    count+=hash_map[tmp]

        return count