hashtable-part02

454 - 四数相加

相关题解参考：https://leetcode.cn/problems/4sum-ii/solutions/65894/chao-ji-rong-yi-li-jie-de-fang-fa-si-shu-xiang-jia/

一开始看是一点思路都没有，又是看了别人的巧妙题解，又是怀疑我是否和大佬一个物种的一天。

sum分为两组，hashmap 存两个数组的和，AB; 然后计算剩余两个数组的和，CD。 

在求出 sum_ab 之后，将sum_ab 作为 dict 的key, 出现的次数作为dict 的value. 计算c, d中任意两数之和的相反数sum_cd.

在dict中查找是否有存在key 为 sum_cd 的，并返回出现次数。

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
        """
        d = {} 
        for i in nums1 :
            for j in nums2:
                if i+j in d :
                    d[i+j] += 1 
                else: 
                    d[i+j] = 1 
            
        count = 0 
        for k in nums3 :
            for l in nums4:
                if -k-l in d:
                    count += d[-k-l]
        return count 

383

def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        d = {} 
        for i in magazine:
            if i in d: 
                d[i] += 1 
            else:
                d[i] = 1 
        
        for i in ransomNote: 
            value = d.get(i)
            if not value :
                return False
            else:
                d[i] -= 1
        
        return True

15 

https://leetcode.cn/problems/3sum/solutions/11525/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/

学不了一点，真的想不出来。。。。。。。

def threeSum(nums) :
    n = len(nums) 
    res=[] 
    if(not nums or n < 3) :
        return res 

    nums.sort() 
    for i in range(n) :
        if (nums[i] > 0) :
            return res 

        if (i>0 and nums[i]==[nums[i-1]]) :
            continue 
        L = i+1 
        R = n-1 
        while(L < R) :
            s = nums[i] + nums[L] + nums[R] 
            if s < 0 : 
                L += 1 
                while L < R and nums[L] == nums[L-1] :
                    L += 1 
            elif s > 0 :
                R -= 1 
                while L < R and nums[R] == nums[R + 1] :
                    R -= 1 
            else : 
                res.append([nums[i], nums[L], nums[R]]) 
                L += 1 
                R -= 1 
                while i < j and nums[i] == nums[i - 1]: i += 1
                while i < j and nums[j] == nums[j + 1]: j -= 1
    return res