25期代码随想录算法训练营第七天 | 454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和

454.四数相加II

使用defaultdict + 哈希表

记录nums1 + nums2的和于_map中，然后对于nums3 + nums4的和，检查是否为_map的相反数。如果是则累加对应的count。

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        _map = defaultdict(int)

        for a in nums1:
            for b in nums2:
                _map[a+b] += 1

        count = 0

        for c in nums3:
            for d in nums4:
                res = - c - d 
                count += _map[res]
        
        return count
                
            

383. 赎金信

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        freq = Counter(magazine)

        for i in ransomNote:
            if freq[i] == 0:
                return False
            else:
                freq[i] -= 1
        
        return True

15. 三数之和

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

        for i, v in enumerate(nums):
            if v > 0:
                return res
            
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            l, r = i + 1, len(nums) - 1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                if total > 0:
                    r -= 1

                elif total < 0:
                    l += 1

                else:
                    res.append([nums[i], nums[l], nums[r]])
                    # 去重需要放在这个else里，因为在这里结果会被append到res上
                    # 我们是需要对return 的结果去重
                    # 如果在上面的if elif里面去重的话，就会出现
                    # 同样符合条件的元组
                    while l < r and nums[r] == nums[r - 1]:
                        r -= 1
                    while l < r and nums[l] == nums[l + 1]:
                        l += 1
                    l += 1
                    r -= 1
        
        return res

18. 四数之和

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

        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            for j in range(i + 1, len(nums)):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                
                l, r = j + 1, len(nums) - 1
                while l < r:
                    total = nums[i] + nums[j] + nums[l] + nums[r]
                    if total > target:
                        r -= 1
                    elif total < target:
                        l += 1
                    else:
                        res.append([nums[i], nums[j], nums[l], nums[r]])
                        while r > l and nums[r] == nums[r - 1]:
                            r -= 1
                        while r > l and nums[l] == nums[l + 1]:
                            l += 1
                        
                        l += 1
                        r -= 1
        return res