Z.H.Chen's Blog
0%

LeetCode——哈希表经典例题

发表于 分类于 ， Valine：
2.1k 4 分钟

242. 有效的字母异位词

  给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例二：

1
2
输入: s = "rat", t = "car"
输出: false

思路：定义一个数组叫做 record，大小为 26就可以了，初始化为0，因为题目规定两个字符串的的字符均是小写字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26

        #记录 s 中的个字母出现的次数
        for i in range(len(s)) :
            record[ord(s[i]) - ord('a')] += 1

        #记录 t 中的个字母出现的次数
        for i in range(len(t)) :
            record[ord(t[i]) - ord('a')] -= 1

        #record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
        for i in range(len(record)) :
            if record[i] != 0 :
                return False

        return True

349. 两个数组的交集

  给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例一：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

思路：使用 set 对两个数组进行去重，然后求交集。

1
2
3
4
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        lst = list(set(nums1) & set(nums2))
        return lst

202. 快乐数

  编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例一：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例二：

1
2
输入：n = 2
输出：false

思路：如果一个数不是快乐数，则其之后的树的平方和一定会出现重复现象的，否则就进入死循环了。所以这道题目使用哈希法，来判断这个 sum 是否重复出现，如果重复了就是 return false， 否则一直找到 sum 为1为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def isHappy(self, n: int) -> bool:
        #计算每次的平方和
        def calculate_happy(num) :
            s = 0
            while num :
                s += (num % 10) * (num % 10)
                num //= 10
            return s 

        #哈希记录平方和
        record = set()
        while True :
            n = calculate_happy(n) 
            if n == 1:
                return True
            #如果出现重复的平方和，说明这个数不是快乐数
            if n in record :
                return False 
            else :
                record.add(n)
        return True

1. 两数之和

  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例一：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例二：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

思路：以元素为 key，下标为 value 对数组进行统计，遍历数组，如果能在字典中找到 target - nums[i] 说明找到了解。

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict_val = dict()
        for idx, val in enumerate(nums) :
            if target - val not in dict_val :
                dict_val[val] = idx
            else :
                return [idx, dict_val[target - val]]

15. 三数之和

  给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

示例一：

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例二：

1
2
输入：nums = []
输出：[]

思路：这道题可以先固定一个数，然后通过解决 两数之和 的方法进行求解，但是在 两数之和 这道题中，我们只需要求解一个解，而这道题可能有多个解，且题目要求不能出现重复的解，因此如果使用哈希表的方法社涉及大量的去重操作。效率低且容易出错，这里介绍双指针的方法，首先将数组排序，然后有一层 for 循环，i从下标0的地方开始，同时定一个下标 left 定义在 i+1 的位置上，定义下标right 在数组结尾的位置上。依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。接下来如果 nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以 right 下标就应该向左移动，这样才能让三数之和小一些。如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到 left 与 right 相遇为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def threeSum(self, nums):
        ans = []
        nums.sort()

        for i in range(len(nums)) :
            #如果第一个数大于0，则找不到解
            if nums[i] > 0 :
                break

            left = i + 1
            #右指针指向数组的末尾
            right = len(nums) - 1

            #对第一个元素去重
            if i > 0 and nums[i] == nums[i - 1] :
                continue 
            
            while left < right :
                total = nums[i] + nums[left] + nums[right]

                #如果和大于0，则要减小和即让右指针左移
                if total > 0 :
                    right -= 1
                #如果和小于0，则要增大和即让左指针右移
                elif total < 0 :
                    left += 1
                else :
                    #找到一组解
                    ans.append([nums[i], nums[left], nums[right]])
                    #对左边去重
                    while left != right and nums[left] == nums[left + 1] :
                        left += 1
                    #对右边去重
                    while left != right and nums[right] == nums[right - 1] :
                        right -= 1
                    #同时收缩左右指针
                    left += 1
                    right -= 1
        return ans

18. 四数之和

  给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

示例 1：

1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例二：

1
2
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

思路：本题跟 三数之和 解法一样，但要注意不要判断 nums[i] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target 是任意值。类似的，五叔之和，六叔之和都可以这样解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans = []
        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 

                left = j + 1
                right = len(nums) - 1

                while left < right :
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total > target :
                        right -= 1
                    elif total < target :
                        left += 1
                    else :
                        ans.append([nums[i], nums[j], nums[left], nums[right]])
                        while left != right and nums[left] == nums[left + 1] :
                            left += 1
                        while left != right and nums[right] == nums[right - 1] :
                            right -= 1
                        left += 1
                        right -= 1
        return ans

454. 四数相加 II

  给你四个整数数组nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

1
2
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

思路：这道题目是四个独立的数组，只要找到 nums[i] + nums[j] + nums[k] + nums[l] = 0 就可以，不用考虑有重复的四个元素相加等于0的情况，因此适合使用哈希表法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        hashmap = {}
        n = len(nums1)
        count = 0
        #哈希统计A和B的数组之和的次数
        for i in range(n) :
            for j in range(n) :
                if (nums1[i] + nums2[j]) not in hashmap :
                    hashmap[nums1[i] + nums2[j]] = 1
                else:
                    hashmap[nums1[i] + nums2[j]] += 1
        
        for k in range(n) :
            for l in range(n) :
                sum_ = nums3[k] + nums4[l]
                #直接相加-(k + l)的次数，因为本道题允许重复的解出现
                if -sum_ in hashmap :
                    count += hashmap[-sum_]

        return count

383. 赎金信

  给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。提示：

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote 和 magazine 由小写英文字母组成

思路：这道题跟 有效的字母异位词 差不多，哈希表法解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        record = [0] * 26
        for i in range(len(magazine)) :
            record[ord(magazine[i]) - ord('a')] += 1
        
        for i in range(len(ransomNote)) :
            record[ord(ransomNote[i]) - ord('a')] -= 1

        for i in range(26) :
            if record[i] < 0 :
                return False
                
        return True