454.四数相加II

思路：
和有效字母异位词类似，先遍历nums1 + nums2，将结果存放至record字典，然后遍历nums3 + nums4

record = defaultdict(lambda : 0)

使用 record = dict() ，尝试访问一个不存在的键时，record 字典会引发一个 KeyError 异常。
所以使用 defaultdict，尝试访问一个不存在的键，该键将自动被创建，并将其值设置为 0（lambda: 0，它返回默认值 0）

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        from collections import defaultdict
        record = defaultdict(lambda : 0)
        cnt = 0

        for i in nums1:
            for j in nums2:
                record[i + j] += 1 # 字典的key为：i+j，value为 +=1
        for i in nums3:
            for j in nums4:
                # 写法1
                if -(i + j) in record.keys(): # 如果 -(i+j)在record.key里，cnt为record.value
                    cnt += record[-(i + j)] # 这里不能是 += 1
                # 写法2
                cnt += record.get(-(i + j), 0)
        return cnt

383. 赎金信

哈希表（数组）

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        record = [0] * 26

        for i in magazine: # 先遍历magazine的字符
            record[ord("a") - ord(i)] += 1
        for i in ransomNote:
            if record[ord("a") - ord(i)] == 0: # 如果magazine的字符不够用，就返回false
                return False
            else:
                record[ord("a") - ord(i)] -= 1
        return True

15. 三数之和

双指针法

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # 需要先排序
        n = len(nums) # 这里不用-1
        result = []

        for i in range(n):
            left = i + 1
            right = n - 1
            if nums[i] > 0: # 排序过后第一个元素大于1，跳出循环
                break
            if i >=1 and nums[i] == nums[i-1]: # 先对i去重,如果前2个元素相等，i+1，这里用i-1来做比较
                continue
            while left < right:
                sum_nums = nums[i] + nums[left] + nums[right]
                if sum_nums > 0:
                    right -= 1
                elif sum_nums < 0:
                    left += 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    while left != right and nums[left] == nums[left + 1]: left += 1 # 对left去重
                    while left != right and nums[right] == nums[right - 1]: right -= 1 # 对right去重
                    left += 1
                    right -= 1
        return result

18. 四数之和

在三数之和的基础上，增加一层循环
更新 剪枝 和 去重 判断逻辑

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort() # 需要先排序
        n = len(nums)
        result = []

        for k in range(n):
            if nums[k] > target and nums[k] > 0 and target > 0: break # 剪枝
            if k > 0 and nums[k] == nums[k-1]: continue # 去重

            for i in range(k+1, n):
                if nums[k] + nums[i] > target and nums[k] + nums[i] > 0 and target > 0: break #剪枝
                if i > k + 1 and nums[i] == nums[i-1]: continue# 去重

                left = i + 1
                right = n - 1

                while left < right:
                    sum_nums = nums[k] + nums[i] + nums[left] + nums[right]
                    if sum_nums > target: # 这里要更新为target
                        right -= 1
                    elif sum_nums < target:
                        left += 1
                    else:
                        result.append([nums[k], nums[i], nums[left], nums[right]])
                        while left != right and nums[left] == nums[left + 1]: left += 1 # 对left去重
                        while left != right and nums[right] == nums[right - 1]: right -= 1 # 对right去重
                        left += 1
                        right -= 1
        return result