四数相加 哈希表

作者

454. 四数相加 II

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        dic1=defaultdict(int)
        dic2=defaultdict(int)
        res=0
        for i in nums1:
            for l in nums2:
                dic1[i+l]+=1
        for i in nums3:
            for l in nums4:
                dic2[i+l]+=1
        for i in dic1:
                if -i in dic2:
                    res+=dic1[i]*dic2[-i]
        return res
优化版
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        dic1=defaultdict(int)
        res=0
        for i in nums1:
            for l in nums2:
                dic1[i+l]+=1
        for i in nums3:
            for l in nums4:
                res+=dic1.get(-(i+l),0)
        return res

发表评论