【chap5-哈希表】用Python3刷《代码随想录》
·
目录
基础知识讲解
哈希表/散列表（Hash Table）：
- 根据关键码的值直接访问数据的数据结构，如数组
- 一般用来快速判断一个元素是否出现在集合中，时间复杂度O(1) （枚举法时间复杂度O(n)）
哈希函数（Hash Function）：
- 哈希函数把数据直接映射为哈希表上的索引（把传入的key映射到符号表的索引上）
- hashCode通过特定编码方式，可以将其他数据格式转化为不同的数值
如果hashCode得到的数值 > 哈希表的最大边界 tableSize-1，为了保证映射出来的索引数值都落在哈希表上，会再次对数值做一个取模操作，保证数据一定可以映射到哈希表上
哈希碰撞：
若数据的数量＞哈希表的大小，就算哈希函数计算的再均匀，也避免不了会有几个数据同时映射到哈希表上同一个索引的位置（多个key映射到相同索引）
两种解决方法：
- 拉链法：发生冲突的元素都被存储在链表中。要选择适当的哈希表大小
- 线性探测法：向下找一个空位放置冲突的数据。一定要保证 tableSize > dataSize
常见的三种哈希结构：
- 数组：哈希值小且范围可控时使用
- set（集合）：哈希数值很大，或数值分布很分散时使用
- map（映射）：是一个 <key, value> 的数据结构，key不可修改，value可以
总结：
- 当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法
- 哈希法牺牲空间换取时间，因为要使用额外的数组、set或者map来存放数据，才能实现快速查找
【数组】242. 有效的字母异位词
数组就是简单的哈希表，但是数组的大小不能无限开辟（使用数组来做哈希的题目，是因为题目都限制了数值的大小）
只包含小写字母的题目，就很适合用数组（初始化为 [0]*26）
题目描述：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词
分析步骤：
- 定义一个数组来记录字符串s里字符出现的次数，数组名叫 record，大小为26（因为字符串中只有小写字符）
- 字符a - 字符z 的ASCII码是26个连续的数值，把字符映射到数组（即哈希表的索引下标）上后，字符a即映射为下标0，字符z即映射为下标25
- 遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做 +1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数统计出来了
- 同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作
- 若record数组有元素不为0，说明字符串s和t一定是谁多了字符或者谁少了字符，return False；如果record数组所有元素都为0，说明字符串s和t是字母异位词，return True
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# 定义一个数组record，记录字符串s中各字符出现次数
record = [0]*26 # 初始化为0，共26个字母
for i in s:
record[ord(i) - ord('a')] += 1
for i in t:
record[ord(i) - ord('a')] -= 1
for i in range(len(record)):
if record[i] != 0:
return False
return True【数组】383. 赎金信
242. 有效的字母异位词：求 字符串a 和 字符串b 是否可以相互组成
383. 赎金信：求 字符串a 能否组成 字符串b，而不用管 字符串b 能不能组成 字符串a
因为题目只有小写字母，可以用一个长度为26的数组记录magazine里字母出现的次数，然后再用 ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
record = [0]*26 # 只有小写英文字母
if len(ransomNote) > len(magazine):
return False
for i in magazine:
record[ord(i) - ord('a')] += 1
for j in ransomNote:
record[ord(j) - ord('a')] -= 1
if record[ord(j) - ord('a')] < 0:
return False
return True【map】49. 字母异位词分组
用哈希表来对字符串进行分组，key为字符串的字母序排列，value为相同排列的所有字符串的数组。遍历结束时，将哈希表的value一起返回即可
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dic = {}
for i in strs:
i_sorted = "".join(sorted(i)) # 对字符串按字母顺序排序
if i_sorted not in dic:
dic[i_sorted] = [i]
else:
dic[i_sorted].append(i)
return list(dic.values())举个栗子：
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
sorted("eat") 的输出是 ['a', 'e', 't']，经过 "".join() 后，输出为 "aet"
这样，把每个单词按字母序排序后的结果作为key，value为排序前的结果
以列表的形式返回字典的所有值：list(dic.values())
【数组】438. 找到字符串中所有字母异位词
思路：哈希（数组）+滑动窗口
- 因为字符串中的字符全是小写字母，可以用长度为26的数组记录字母出现的次数
- 设 m = len(s), n = len(p)。记录p字符串的字母频次p_cnt，和s字符串前n个字母的字母频次s_cnt
- 若p_cnt和s_cnt相等，则找到第一个异位词索引 0
- 继续遍历s字符串索引为[n, m)的字母【这里是滑动窗口的右窗口索引下标】，在s_cnt中每次增加一个新字母，去除一个旧字母
- 判断p_cnt和s_cnt是否相等，相等则在返回值result中新增异位词索引 i - n + 1
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
m, n = len(s), len(p)
result = []
if m < n:
return []
s_cnt = [0]*26
p_cnt = [0]*26
for i in range(n):
p_cnt[ord(p[i]) - ord('a')] += 1
s_cnt[ord(s[i]) - ord('a')] += 1
# 第一个窗口
if p_cnt == s_cnt: # 说明s的前len(p)个字符，就是p的字母异位词
result.append(0) # 返回起始索引0
for i in range(n,m): # i指向字符的最后一位(窗口的右指针)
s_cnt[ord(s[i-n]) - ord('a')] -= 1 # 滑动窗口，剃掉之前窗口的开始位置
s_cnt[ord(s[i]) - ord('a')] += 1 # 新加进来的字母
if s_cnt == p_cnt:
result.append(i-n+1) # 新窗口起始位置
return result 【map】350. 两个数组的交集II
思路：两个字典分别记录下两个数组里的值（key）和出现次数（value），遍历其中一个字典，若其key在另一个字典中也出现过，返回这个key，且这个key的次数为该key在两个字典中对应的较小value
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
dic1 = {}
dic2 = {}
for i in nums1:
if i in dic1:
dic1[i] += 1
else:
dic1[i] = 1
for j in nums2:
if j in dic2:
dic2[j] += 1
else:
dic2[j] = 1
res = []
for i in dic1:
if i in dic2:
res = res + [i]*min(dic1[i], dic2[i])
return res【set】349. 两个数组的交集
如果哈希值比较少/特别分散/跨度非常大，使用数组就造成空间的极大浪费。使用数组来做哈希的题目，是因为题目都限制了数值的大小
直接使用set不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的
这题在提示中限制了nums的长度≤1000，故本题可以用数组，也可以用set（区别于242题）来做哈希表
（一）set
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
result = set() # 自动去重
num_size = set(nums1) # 把nums1转换为哈希表
for i in nums2:
if i in num_size: # 在哈希表里是否出现过
result.add(i)
return list(result)这题注意，往set里增加元素的方法是add()，以及 set可以自动去重 这两个点即可
（二）数组
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
t1 = [0]*1001
result = set()
# 把nums1处理成哈希表的结构
for i in range(len(nums1)):
t1[nums1[i]] = 1 # 记录nums1里所有出现过的元素
for i in range(len(nums2)):
if t1[nums2[i]] == 1: # 判断哈希表t1里是否出现过nums2的元素
result.add(nums2[i])
return list(result)总结：
- 用set，每往里增加一个值都要做哈希运算，转变为内部存储的值，还要开辟内部新的空间
- 而数组直接用下标来做哈希映射，故若nums的长度和大小有限制时，优先用数组
【set】202. 快乐数
求和过程中sum会重复出现，使用哈希法（定义一个集合set）来判断这个sum是否重复出现，若重复则无限循环、始终到不了1（返回False），否则一直找到 sum=1 为止
class Solution:
# 先定义一个算每位平方和的函数
def calculate(self, n: int):
sum = 0
for i in range(len(str(n))):
sum += int(str(n)[i])**2
return sum
def isHappy(self, n: int) -> bool:
record = set() # 定义一个集合，判断sum是否出现过
res = self.calculate(n)
while res != 1:
if res in record: # 若出现过，说明无限循环但始终变不到1
return False
record.add(res) # 将结果添加进集合中
res = self.calculate(res)
return True【map】1. 两数之和
- 242. 有效的字母异位词这道题目是用数组作为哈希表来解决哈希问题
- 349. 两个数组的交集这道题目是通过set作为哈希表来解决哈希问题
使用数组和set的局限：
- 数组的长度是受限制的，如果元素很少而哈希值很大，则会造成内存空间的浪费
- set是一个集合，里面放的元素只能是一个key
而本题不仅要判断y是否存在，还要记录y的下标位置，因为要返回x和y的下标，因此要用另一种数据结构 — map，它是一种 <key, value> 的存储结构，可以用key保存数值，value保存数值所在的下标
思路：需判断一个元素是否遍历过。把遍历过的元素加到一个集合里（map存放遍历过的元素），每次遍历一个新的位置之后，判断想要寻找的这个元素是否在这个集合里出现过（元素为key，下标为value，map结构即查找key是否在map里出现过）
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 定义一个字典存放遍历过的元素
dic = {}
for i in range(len(nums)):
s = target - nums[i] # 要去字典里查询的值为s
if s in dic:
return [dic.get(s), i]
dic[nums[i]] = i # key是元素，value是下标
return []
- 查一个字典中有没有为某值的key，直接用关键字in即可
- 字典中增加一对键值对，直接 dict[key] = value 即可
错误写法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(nums)):
if nums[i] not in dic:
dic[nums[i]] = i
if target - nums[i] in dic:
return [i, dic[target - nums[i]]]这种写法会导致同一个元素被用两次，与题意矛盾（题目明确说了，不能使用两次相同的元素）。如：
nums = [3, 2, 4], target = 6
# 错误写法的代码执行过程：
i=0, nums[i]=3
1. dic中没有3，dic={3:0}
2. target-nums[i]=3 在dic中吗？在！dic[3]=0
3. 返回 [0, 0] ❌（不应该用同一个元素）
# 实际上正确答案应该是 [1, 2] (2+4=6)【map】454. 四数相加II
思路：
- 定义一个字典，key为a和b两数之和，value为a和b两数之和出现的次数
- 遍历A、B数组，统计两个数组的元素之和及出现的次数，并放到字典中
- 定义int类型的变量count，用来统计a+b+c+d=0出现的次数
- 在遍历C、D数组时，如果0-(c+d)在字典中出现，就使用count统计字典中key对应的value，即两数之和出现的次数
- 返回统计值count
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
dic = {} # key为遍历nums1和nums2数组得到的两数之和，value为和的出现次数
for a in nums1:
for b in nums2:
if a+b not in dic:
dic[a+b] = 1
else:
dic[a+b] += 1
count = 0
for c in nums3:
for d in nums4:
target = 0-(c+d) # 因为a+b+c+d=0
if target in dic:
count += dic[target]
return count【双指针】15. 三数之和
思路：双指针法，而非哈希法（因为要剔除重复的三元组）
- 首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 在i+1的位置上（i 的后一个），定义下标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相遇为止
重点：如何去重？
- 我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的【nums[i] == nums[i+1] 时continue，是去掉有重复元素的三元组】，所以这里是有两个重复的维度，故：
if nums[i] == nums[i-1] and i>0:
continue- 后两个数的去重逻辑，应放在找到一个三元组之后
while right > left and nums[left] == nums[left+1]:
left += 1
while right > left and nums[right] == nums[right-1]:
right -= 1完整代码：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort() # 保证数组有序
for i in range(len(nums)):
if nums[i] > 0: # 排完序后若第一个数都>0，则不可能存在三数之和为0
return result
if nums[i] == nums[i-1] and i>0: # 对a去重
continue
left, right = i+1, len(nums)-1
while left < right: # 不能=，若left=right，则为同一个数，不是三数之和了
sums = nums[i] + nums[left] + nums[right]
if sums > 0:
right -= 1
elif sums < 0:
left += 1
else:
result.append([nums[i], nums[left], nums[right]])
# 以下为后面两个数的去重逻辑，应放在找到一个三元组之后
while right > left and nums[left] == nums[left+1]: # 对b去重
left += 1
while right > left and nums[right] == nums[right-1]: # 对c去重
right -= 1
right -= 1
left += 1
return result【双指针】18. 四数之和
注意：target 不一定 =0，也可以为负数（而两个负数相加是会越加越小的）
- 因此，这里剪枝时，需要加大于0的判断条件
思路：双指针法，在三数之和外面再套一层for循环，顺序：k、i（k后一位）、left（i后一位）、right（数组最后一位）
- 三数之和：一层for循环遍历，得到的 nums[i] 为确定值，然后循环内有 left 和 right 下标作为双指针，找出 nums[i] + nums[left] + nums[right] == 0。时间复杂度 O(n^2)
- 四数之和：两层for循环遍历，得到的 nums[k] + nums[i] 为确定值，依然是循环内有 left 和 right 下标作为双指针，找到 nums[k] + nums[i] + nums[left] + nums[right] == target。时间复杂度 O(n^3)
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
result = []
nums.sort() # 先将数组排序
for k in range(len(nums)):
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, len(nums)):
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, right = i+1, len(nums)-1
while left < right:
sums = nums[k] + nums[i] + nums[left] + nums[right]
if sums < target:
left += 1
elif sums > target:
right -= 1
else:
result.append([nums[k], 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 result
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献6条内容
所有评论(0)