代码随想录算法训练营Day07｜454、383、15、18

454. 四数相加 II

• 先计算出前两个数组和的组合
• 再根据后两个数组双重迭代找出前一步中对应组合的加和来判断组合数，如无则0

from collections import defaultdict
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        rec,cnt = defaultdict(lambda:0),0
        for i in nums1:
            for j in nums2:
                rec[i+j] += 1
        for i in nums3:
            for j in nums4:
                cnt += rec.get(-(i+j),0)
        return cnt

383. 赎金信

• 一开始写的判断条件是dict1==dict2，但是其实应该dict1包含于dict2即可，所以对dict1遍历，看看dict1中的每个字母和个数是否小于dict2中该字母的个数，如果没有或者小于了就返回false。如果遍历完没有问题就可以返回True啦。

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        dict1 = self.convert(ransomNote) 
        dict2 = self.convert(magazine)
        for char,count in dict1.items():
            if char not in dict2 or dict2[char] < count:
                return False
        return True
        
    def convert(self,input_str:str) -> dict:
        if not isinstance(input_str, str):
            raise TypeError("Input must be a string")
        return dict(Counter(input_str))

15. 三数之和

• 三指针的方式来解决，其实就是把i迭代，然后使用双指针从左往右、从右往左来获得==0的一个组合

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i in range(len(nums)):
            if nums[i] > 0:
                return res
        
            if i > 0 and nums[i]==nums[i-1]:
                continue
            
            left = i+1
            right = len(nums)-1

            while right>left:
                sum_ = nums[i] + nums[left] + nums[right]
                if sum_ < 0:
                    left += 1
                elif sum_ >0:
                    right -=1
                else:
                    res.append([nums[i],nums[left],nums[right]])
                    
                    while right > left and nums[right] == nums[right-1]:
                        right -=1
                    while right > left and nums[left] == nums[left+1]:
                        left += 1
                    right -= 1
                    left += 1
        return res

18. 四数之和

• 留个坑，下次用双指针法再做一遍

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        freq = {}
        for num in nums:
            freq[num] = freq.get(num,0)+1
        
        ans = set()
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                for k in range(j+1,len(nums)):
                    val = target-(nums[i]+nums[j]+nums[k])
                    if val in freq:
                        count = (nums[i]==val)+(nums[j]==val)+(nums[k]==val)
                        if freq[val] > count:
                            ans.add(tuple(sorted([nums[i],nums[j],nums[k],val])))
        return [list(x) for x in ans]