哈希表 Part02 笔记#

1
class Solution:
2
    # 四数字相加问题可以转化为两个两数相加的问题
3
    # 即将 nums1 和 nums2 的所有两数之和存入一个哈希表中，nums3 和 nums4 的所有两数之和则需要查找哈希表中是否存在对应的负数和
4
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
5
        record = {}
6
        # 计算 nums1 和 nums2 的所有两数之和，并记录出现的次数
7
        for num1 in nums1:
8
            for num2 in nums2:
9
                record[num1 + num2] = record.get(num1 + num2, 0) + 1
10

11
        res = 0
12
        # 对于 nums3 和 nums4 的每一对数字，计算它们的和，并查找哈希表中是否存在对应的负数和
13
        for num3 in nums3:
14
            for num4 in nums4:
15
                need = 0 - (num3 + num4)
16
                if need in record:
17
                    res += record[need]
18
        return res

1
class Solution:
2
    # 这个是和 LeetCode 242 有效的字母异位词 类似的题目
3
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
4
        record = {}
5
        # 统计 magazine 中每个字母出现的次数
6
        for char in magazine:
7
            record[char] = record.get(char, 0) + 1
8
        # 遍历 ransomNote 中的每个字符，依次判断是否可以匹配
9
        for char in ransomNote:
10
            if char in record and record[char] > 0:
11
                record[char] -= 1
12
            else:
13
                return False
14
        return True

1
class Solution:
2
    def threeSum(self, nums: List[int]) -> List[List[int]]:
3
        nums.sort()  # 排序后方便使用双指针和去重
4
        res = []
5
        for i in range(len(nums) - 2):
6
            left = i + 1
7
            right = len(nums) - 1
8
            # 如果当前数字大于0，则后续的数字都大于0，无法满足三数之和为0
9
            if nums[i] > 0:
10
                break
11
            # ⚠️ 注意这里需要跳过重复的数字，避免结果中出现重复的三元组
12
            if i > 0 and nums[i] == nums[i - 1]:
13
                continue
14
            while left < right:
15
                total = nums[i] + nums[left] + nums[right]
16
                if total == 0:
17
                    res.append([nums[i], nums[left], nums[right]])
18
                    # ⚠️ 跳过重复数字，确保三元组唯一
19
                    while left < right and nums[left] == nums[left + 1]:
20
                        left += 1
21
                    while left < right and nums[right] == nums[right - 1]:
22
                        right -= 1
23
                    # 移动双指针
24
                    left += 1
25
                    right -= 1
26
                elif total < 0:
27
                    left += 1
28
                else:
29
                    right -= 1
30
        return res

1
class Solution:
2
    # 四数之和可以转化为三数之和的问题
3
    # 首先对数组进行排序，然后固定前两个数字，使用双指针查找后两个数字
4
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
5
        nums.sort()  # 排序以便使用双指针法
6
        res = []
7
        for i in range(len(nums) - 3):
8
            # 如果当前数字加上后三个最小的数字的和都大于目标值，则直接跳出循环
9
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
10
                break
11
            # 如果当前数字加上后三个最大的数字的和都小于目标值，则跳过当前数字
12
            if nums[i] + nums[-1] + nums[-2] + nums[-3] < target:
13
                continue
14
            if i > 0 and nums[i] == nums[i - 1]:
15
                continue
16
            for j in range(i + 1, len(nums) - 2):
17
                # 如果当前数字加上后面两个最小的数字的和都大于目标值，则跳出循环
18
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
19
                    break
20
                # 如果当前数字加上后面两个最大的数字的和都小于目标值，则跳过
21
                if nums[i] + nums[j] + nums[-1] + nums[-2] < target:
22
                    continue
23
                if j > i + 1 and nums[j] == nums[j - 1]:
24
                    continue
25
                left = j + 1
26
                right = len(nums) - 1
27
                while left < right:
28
                    total = nums[i] + nums[j] + nums[left] + nums[right]
29
                    if total == target:
30
                        res.append([nums[i], nums[j], nums[left], nums[right]])
31
                        # ⚠️ 跳过重复数字，确保四元组唯一
32
                        while left < right and nums[left] == nums[left + 1]:
33
                            left += 1
34
                        while left < right and nums[right] == nums[right - 1]:
35
                            right -= 1
36
                        # 移动双指针
37
                        left += 1
38
                        right -= 1
39
                    elif total > target:
40
                        right -= 1
41
                    else:
42
                        left += 1
43
        return res