Day 7 哈希: 454. 四数相加 II, 383. 赎金信, 15. 三数之和, 18. 四数之和

454. 四数相加 II

• 思路
  • example
  • 四个数组相同长度
  • 第一步：brute-force:
  • hash: dict
    • record[num] = freq

第二步：
第三步：(nums1[i]+nums2[j]) + (nums3[k]+nums4[l])，

• 复杂度. 时间：, 空间:

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        n = len(nums1) 
        record = collections.defaultdict(int) 
        for i in range(n):
            for j in range(n):
                record[nums1[i]+nums2[j]] += 1 
        res = 0
        for k in range(n):
            for l in range(n):
                if -(nums3[k] + nums4[l]) in record:
                    res += record[-(nums3[k] + nums4[l])]
        return res 

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        record = collections.defaultdict(int)  
        for num1 in nums1:
            for num2 in nums2:
                record[num1+num2] += 1
        res = 0
        for num3 in nums3:
            for num4 in nums4:
                if record[-(num3+num4)] > 0:
                    res += record[-(num3+num4)] # !!!
        return res    

383. 赎金信

• 思路
  • example
  • hash: dict
    • record[ch] = freq

先遍历模式串magazine

• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        table = collections.defaultdict(int)
        for ch in magazine:
            table[ch] += 1
        for ch in ransomNote:
            table[ch] -= 1
            if table[ch] < 0:
                return False  
        return True  

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        record = collections.defaultdict(int)   
        for ch in magazine:
            record[ch] += 1 
        for ch in ransomNote:
            record[ch] -= 1
            if record[ch] < 0:
                return False  
        return True 

15. 三数之和

• 思路
  • example
  • a + b + c = 0
  • 用hash的话去重问题更麻烦。
  • 双指针, --><--
    • 去重：(用排序配合)
      • a: nums[i] == nums[i-1]
      • b and c: while-loop moving left and right
• 复杂度. 时间：, 空间:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]: # 去重１
                continue  
            target = -nums[i]
            left, right = i + 1, n - 1
            while left < right:
                sum_ = nums[left] + nums[right]
                if sum_ == target:
                    res.append([nums[i], nums[left], nums[right]])
                    left += 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    right -= 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1
                elif sum_ < target: 
                    left += 1
                else:
                    right -= 1
        return res

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)  
        nums.sort()   
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue   
            target = -nums[i] 
            left, right = i+1, n-1
            while left < right:
                sum_ = nums[left] + nums[right] 
                if sum_ < target:
                    left += 1
                elif sum_ > target:
                    right -= 1
                else: 
                    res.append([nums[i], nums[left], nums[right]]) 
                    left += 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    right -= 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1
        return res    

18. 四数之和

• 思路
  • example
  • 双指针，三数之和推广
  • 去重，三个层面: a, b, 以及c and d
• 复杂度. 时间：, 空间:

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res  = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]: # 同层去重
                continue 
            for j in range(i+1, n):
                if j > i + 1 and nums[j] == nums[j-1]: # 同层去重
                    continue 
                target2 = target - (nums[i] + nums[j])
                left, right = j + 1, n - 1
                while left < right: 
                    sum_ = nums[left] + nums[right]
                    if sum_ == target2:
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        left += 1
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                        right -= 1
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
                    elif sum_ < target2:
                        left += 1
                    else:
                        right -= 1
        return res 

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums) 
        res = []
        nums.sort()  
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue  
            for j in range(i+1, n):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue  
                target2 = target-(nums[i] + nums[j]) # !!!
                left, right = j+1, n-1
                while left < right:
                    sum_ = nums[left] + nums[right] 
                    if sum_ < target2:
                        left += 1
                    elif sum_ > target2:
                        right -= 1
                    else:
                        res.append([nums[i], nums[j], nums[left], nums[right]]) 
                        left += 1
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                        right -= 1
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
        return res