LeetCode刷题3：哈希篇

提示：本篇共8道力扣题目供大家食用，时间自行把控~

算法刷题系列

• LeetCode刷题1：数组篇
• LeetCode刷题2：链表篇

---

---

作者有话说

  1、本篇是算法刷题系列文章的第 3 篇，写此系列的目的是为了让自己对题目的理解更加深刻。

  2、本系列博客主要参考了卡哥的 代码随想录博客 以及 卡哥本人B站讲解的视频 代码随想录B站视频 ，强烈推荐给大家，因为本人学习中 Python为主，因此博客主要由 Python 代码呈现给大家，需要其他语言的版本，卡哥博客链接自取。

---

一、哈希表

1.1 python字典知识

• 在 Python 中，字典是一系列 键值对 。每个键都与一个值相关联，你可以使用键来访问与之相关联的值。与键相关的值可以是数字、字符串、列表乃至字典。键值对 对是两个相关联的值。指定键时，Python将返回与之相关联的值。键和值之间用冒号分隔，键值对之间用逗号分割。如下所示：

1.1.1 字典定义

favorite_languages= {
		'jen': 'Python',
		'sarah': 'C++',
		'jake': 'Go',
		'jane': 'Java',
}
1
2
3
4
5
6

1.1.2 字典基本操作

• 访问字典值； 要获取与键相关的值，只需指定字典名和放在方括号内的键，即可。

print(favorite_languages['jake'])
# 输出：
Go
1
2
3

• 添加键值对； 依次指定字典名、用方括号括起的键和相关联的值，如：在字典favorite_languages中添加 Tom 最喜欢的语言是 Html 。

favorite_languages['Tom'] = 'Html'
print(favorite_languages)
# 输出
{'jen': 'Python', 
'sarah': 'C++', 
'jake': 'Go', 
'jane': 'Java', 
'Tom': 'Html'}
1
2
3
4
5
6
7
8

• 修改字典中的值； 指定字典名、用方括号括起来要修改值的键名，然后使用赋值号 = 赋予新值即可。如：将字典favorite_languages 中添加 Tom 最喜欢的语言改为是 R 。

favorite_languages['Tom'] = 'R'
print(favorite_languages['Tom'])
# 输出
R
1
2
3
4

• 删除键值对； 使用 del语句 将相应的键值对彻底删除。使用时，必须指定字典名和要删除的键，删除 Tom 的例子如下所示。

del favorite_languages['Tom']
print(avorite_languages)
# 输出
{
		'jen': 'Python',
		'sarah': 'C++',
		'jake': 'Go',
		'jane': 'Java',
}
1
2
3
4
5
6
7
8
9

• 遍历字典； 包括：遍历键值对；遍历所有键；遍历所有值。

# 遍历键值对
for name, language in favorite_languages.items():
	print(name+"'s favorite language is " + language)
# 输出：
jen's favorite language is Python
sarah's favorite language is C++
jake's favorite language is Go
jane's favorite language is Java

# 遍历所有键
for name in favorite_languages.keys():
	print(name)
# 输出：
jen
sarah
jake
jane

# 遍历所有值
for language in favorite_languages.values():
	print(language)
# 输出：
Python
C++
Go
Java
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

1.2 哈希表

• 定义： 哈希表（英文名字为 Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指 Hash table 就可以了）。简单理解就是字典。 一般哈希表都是用来快速判断一个元素是否出现集合里。
• 用途： 当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
• 哈希碰撞： 如果 两个物品A和B 都映射到了 索引下标 1 的位置，这一现象叫做 哈希碰撞。一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

• 拉链法： 在发生冲突的 索引1 的位置后面联接一个链表，然后把发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到物品A和B了。注意：拉链法就是要选择适当的哈希表的大小。
• 线性探测法： 使用线性探测法，一定要保证 tableSize(哈希表大小) 大于 dataSize(数据规模) 。 例如：冲突的位置，放了 物品A，那么就向下找一个空位放置 物品B 的信息。

• 参考链接： 哈希碰撞相关内容
• 常见的三种哈希结构： 数组、set (集合)、map(映射)。

二、经典题目

2.1 LeetCode242. 有效的字母异位词

• 原题地址： 242.有效的字母异位词
• 题目描述： 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意： 若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
• 解题思路： 共有两种方法：排序和哈希。

法1排序法： 根据题意可知，只有字符串 s 和 t 长度相同时，才有可能是字母异位词。因此将字符串 s 和 t 进行排序，然后对比字符串 s 和 t 是否相同就可以解决本题。
法2哈希法： 借助数组，因为 a~z 的 ASCII码 是连续的，因此可以 a可以映射为 数组下标0的位置，z可以映射为 数组下标25的位置。因此，我们可以先统计 字符串s 中每个字母出现的频次，然后在遍历 字符串t 将出现的字母频次拿刚刚创建的数组做减法。若最后数组是全零数组，就证明字符串 s 和 t 是有效的字母异位词，否者则不是，代码见下方。

• 代码如下：

2.1.1 方法一：排序法

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        len_s = len(s)
        len_t = len(t)
        if len_s != len_t:
            return False
        else:
            s = sorted(s)
            t = sorted(t)
            for i in range(len_s):
                if s[i] == t[i]:
                    continue
                else:
                    return False
            return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.1.2 方法二：哈希法

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        hashTable = [0] * 26
        # 1、创建数组，记录s中的字母频次
        for i in s:
            hashTable[ord(i) - ord("a")] += 1
        # 2、做减法
        for i in t:
            hashTable[ord(i) - ord("a")] -= 1
        # 3、检查数组中的数据, hashTable数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
        for i in range(26):
            if hashTable[i] != 0:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2 LeetCode349. 两个数组的交集

• 原题地址： 349. 两个数组的交集
• 题目描述： 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
• 解题思路： 使用 set 对两个数组进行去重，然后遍历较短的数组并与另一数组中的数字进行比较，若相同则添加到 ans 数组中，遍历结束返回 ans 数组即可，下面给出参考代码，可简化。
• 代码如下：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1 = list(set(nums1))
        nums2 = list(set(nums2))
        len_1 = len(nums1)
        len_2 = len(nums2)
        ans = []
        if len_1 > len_2:
            for i in range(len_2):
                if nums2[i] not in nums1:
                    continue
                else:
                    ans.append(nums2[i])
        else:
            for i in range(len_1):
                if nums1[i] not in nums2:
                    continue
                else:
                    ans.append(nums1[i])
        return ans        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.3 LeetCode202. 快乐数

• 原题地址： 202. 快乐数
• 题目描述： 编写一个算法来判断一个数 n 是不是快乐数。快乐数的定义如下：

「快乐数」 定义为：

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

• 解题思路： 对所给数字取各个位上的单数，然后求和并将值赋给 sum，建立record = set() 记录过程中产生的存 sum值，若 record 中有重复的元素，则返回 False ，否则继续计算，直到为 1 返回 True 。
• 代码如下：

class Solution:
    def getSum(self, n):
        sum_ = 0
        # 从个位上依次进行取值，求和
        while n:
            sum_ += (n % 10) * (n % 10)
            n //= 10
        return sum_
    def isHappy(self, n: int) -> bool:
        # 记录中间结果
        record = set()
        while True:
            n = self.getSum(n)
            if n == 1:
                return True
            # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数
            if n in record:
                return False
            else:
                record.add(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.4 LeetCode1. 两数之和

• 原题地址： 1. 两数之和
• 题目描述： 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
• 解题思路： 这里共有三种解法：1、暴力双循环（这里不再讨论）；2、排序+双指针；3、哈希

2.4.1 法一：排序+双指针

• 解题思路： 因为排序的原因，为了保存下标信息另开了一个数组。在新开辟的数组上使用双指针法进行遍历，找到满足题意的数值，然后在原始数组上取出下标值返回即可。时间复杂度 O（nlogn），空间复杂度O（n）。
• 代码如下： 这里的if k >= p 这个判断语句是为了规避相同元素的情况，如：nums=[2,3,3,4,5],target=6 在 pop 出第一个 3 之后其实 nums 被更新了，后面的 3 的位置其实往前走了一位，那么它在 原nums 中的位置就应该是现在位置 +1 呀。参考链接

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 双指针 
        left = 0
        right = len(nums) - 1
        temp = nums.copy()
        temp.sort()
        while left < right:
            sum_ = temp[left] + temp[right]
            if sum_ > target:
                right -= 1
            elif sum_ < target:
                left += 1
            else:
                break
        # 返回原数组的下标
        p=nums.index(temp[left])
        nums.pop(p)
        k=nums.index(temp[right])
        if k>=p:
            k=k+1
        return [p,k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.4.2 法二：哈希法

• 解题思路： 字典哈希，遍历数组，将 target-num[index] 的值存在哈希表中。在遍历数组的时候，只需要向hashtable 去查询是否有和目前遍历元素比配的数值，如果有，就找到了匹配对，如果没有，就把目前遍历的元素放进hashtable 中，因为hashtable 存放的就是我们访问过的元素。
• 代码如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 哈希法
        hashtable = dict()
        for index, value in enumerate(nums):
            if target - value in hashtable:
                return [hashtable[target-value], index]
            else:
                hashtable[value] = index
        return []
1
2
3
4
5
6
7
8
9
10

2.5 LeetCode454. 四数相加 II

• 原题地址： 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、首先定义一个 字典哈希，key放 a 和 b 两数之和，value 放 a 和 b 两数之和出现的次数。
2、遍历 大A 和 大B 数组，统计两个数组元素之和，和出现的次数，放到哈希表中。
3、定义变量 count，用来统计 a+b+c+d = 0 出现的次数。
4、再遍历 大C 和 大D 数组，找到如果 0-(c+d) 在哈希表中出现过的话，就用 count 把哈希表中 key 对应的 value也就是出现次数统计出来。
5、最后返回统计值 count 就可以了

• 代码如下：

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        hashmap = dict()
        # 统计 a、b 两个数组中的元素和，以及次数
        for n1 in nums1:
            for n2 in nums2:
                if n1 + n2 in hashmap:
                    hashmap[n1+n2] += 1
                else:
                    hashmap[n1+n2] = 1
        # 找到如果 `0-(c+d)` 在哈希表中出现过的话，就用 `count` 把哈希表中 `key` 对应的 `value`也就是出现次数统计出来。
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = 0 - (n3+n4)
                if key in hashmap:
                    count += hashmap[key]
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.6 LeetCode383. 赎金信

• 原题地址： 383. 赎金信
• 题目描述： 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。
• 解题思路： 此题与 242. 有效的字母异位词 解题思路如出一辙。用一个长度为 26的数组 去记录 magazine 里字母出现的次数。然后再用 ransomNote去验证这个数组是否包含了 ransomNote 所需要的所有字母即可。
• 代码如下：

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        hashtable = [0] * 26
        for x in magazine:  
            hashtable[ord(x) - ord('a')] += 1
        for x in ransomNote:  
            if hashtable[ord(x) - ord('a')] == 0:  
                return False
            else:
                hashtable[ord(x) - ord('a')] -= 1
        return True
1
2
3
4
5
6
7
8
9
10
11

2.7 LeetCode15. 三数之和

• 原题地址： 15. 三数之和
• 题目描述： 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
• 解题思路： 哈希法去重较为复杂，感兴趣的同学可以去代码随想录网站看题解 —> 点击跳转哈希解法。这里将给出双指针解法。严格来说，本体相当于是三指针，使用for循环遍历数组时有一个 i，代表三数中的第1个数，left = i + 1，代表第2个数，right = len(nums) - 1，代表第3个数 。注意：遍历数组前要将原始数组进行排序。 sum_ = nums[i] + nums[left] + nums[right]，代表三数之和，通过判断 sum_ 与 0 的关系从而将满足题意的结果放入结果集 result 中。关于去重的相关逻辑，建议大家观看 代码随想录：三数之和去重逻辑 。
• 代码如下：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # 存放结果集
        result = []
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            # 去重
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:
                sum_ = nums[i] + nums[left] + nums[right]
                if sum_ > 0:
                    right -= 1
                elif sum_ < 0:
                    left += 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    # 去重，
                    while left != right and nums[right] == nums[right - 1]: 
                        right -= 1
                    while left != right and nums[left] == nums[left + 1]:
                        left += 1
                    left += 1
                    right -= 1
        return result     
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

2.8 LeetCode18. 四数之和

• 原题地址： 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 ；
• 你可以按 任意顺序 返回答案 。

• 解题思路： 与三数之和方法类似，只是多了一层for循环，难点在于去重，这里推荐大家看代码随想录关于本题的题解视频。四数之和题解视频版
• 代码如下：

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  # 对nums[i]去重
            for k in range(i+1, n):
                if k > i + 1 and nums[k] == nums[k-1]: continue  # 对nums[k]去重
                p = k + 1
                q = n - 1

                while p < q:
                    if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                    elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                    else:
                        res.append([nums[i], nums[k], nums[p], nums[q]])
			# 对nums[p]和nums[q]去重
                        while p < q and nums[p] == nums[p + 1]: p += 1
                        while p < q and nums[q] == nums[q - 1]: q -= 1
                        p += 1
                        q -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三、推荐题目

• 49.字母异位词分组
• 438.找到字符串中所有字母异位词
• 350.两个数组的交集 II

---

总结

  哈希表篇到这里就结束了，若文章中有表述不当的地方还望大家多多指出，字符串篇见吧。