1 哈希表理论基础
1.1 哈希表
哈希表是根据关键码的值而直接进行访问的数据结构。一般哈希表都是用来快速判断一个元素是否出现集合里。
1.2 哈希函数
哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值。如果hashCode得到的数值大于tableSize，此时为了保证映射出来的索引数值都落在哈希表上，会再次对数值做一个取模的操作。
好几个名字同时映射到哈希表同一个索引下标的位置，叫哈希碰撞。
一般有两种解决方法， 拉链法和线性探测法。
拉链法
发生冲突的元素都被存储在链表中。拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
线性探测法
使用线性探测法，一定要保证tableSize大于dataSize，依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置放了小李，那么就向下找一个空位放置小王的信息，如图所示：
1.3 常见的三种哈希结构
- 数组
- set （集合）
- map(映射)
在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：
| 集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
| std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) | O(logn) |
| std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
| 映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(logn) | O(logn) |
| std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
map 是一个key-value的数据结构，map中对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的。
1.4 总结
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
2 有效的字母异位词*
题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
**注意：**若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
说明: 字符串只包含小写字母。
示例 1:
输入:s = "anagram",t = "nagaram"
输出: true
示例 2:
输入:s = "rat",t = "car"
输出:false
思路
- 数组
- defaultdict
- Counter
数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个大小为26的数组record，来记录字符串s里字符出现的次数。需要把字符映射到数组索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
在遍历字符串s的时候，**只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，**这样就将字符串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 = [0] * 26
for i in s:
#并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
record[ord(i) - ord("a")] += 1
for i in t:
record[ord(i) - ord("a")] -= 1
for i in range(26):
if record[i] != 0:
#record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return False
return True
时间复杂度: O(n)，空间复杂度: O(1)
defaultdict使得在处理字典时更加方便，无需在访问不存在的键之前检查键是否存在，而是可以直接使用它们。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
from collections import defaultdict
# 创建一个 defaultdict，指定默认值为 int 类型，即默认值为 0
s_dict = defaultdict(int)
t_dict = defaultdict(int)
for x in s:
s_dict[x] += 1 # 访问不存在的键不会引发 KeyError，而是使用默认值 0 创建该键，可以在不提前设置默认值的情况下递增不存在的键的值
for x in t:
t_dict[x] += 1
return s_dict == t_dict
Counter 是 Python 中 collections 模块中的一个类，它用于计数可哈希对象（hashable objects）的出现次数。Counter 返回一个字典，其中键是可哈希对象，而值是该对象在输入序列中出现的次数。Counter 是一种非常方便的工具，特别适用于统计元素的频率。
class Solution(object):
def isAnagram(self, s: str, t: str) -> bool:
from collections import Counter
a_count = Counter(s)
b_count = Counter(t)
return a_count == b_count
3 两个数组的交集
题目：给定两个数组 nums1 和 nums2 ，返回它们的交集 。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
思路
要求不重复，可以用set
- 使用字典和集合
- 使用集合*
- 交集操作：
&，用于获取两个集合的共同元素，返回一个新集合，包含两个集合中都存在的元素。 - 并集操作：
|，表示两个集合的合并，返回包含两个集合中所有不重复元素的新集合。 - 差集操作：
-，用于从一个集合中移除另一个集合中包含的元素，返回一个新集合，包含在第一个集合中但不在第二个集合中的元素。 - 对称差集操作：
^，用于获取两个集合中不重复的元素，返回一个新集合，包含只存在于一个集合中的元素。
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: from collections import defaultdict dict = defaultdict(int) # 使用哈希表存储一个数组中的所有元素 for i in nums1: dict[i] += 1union = set() # 使用集合存储结果 for i in nums2: if i in dict: union.add(i) return list(union) # 记得转回list
时间复杂度：O(n)，空间复杂度：O(n)
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
tips：
思考：为什么不直接所有题目都用set？
直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算。不要小瞧这个耗时，在数据量大的情况，差距是很明显的。
4 快乐数*
题目：编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
思路**
题目中说了会无限循环，也就是说求和的过程中，sum会重复出现，这对解题很重要。
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
- 集合解法一（divmod
- 集合解法二（字符串↔int
- 集合解法三（精简**
class Solution: def isHappy(self, n: int) -> bool: record = set()while True: n = self.get_sum(n) if n == 1: return True # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数 if n in record: return False else: record.add(n) def get_sum(self,n: int) -> int: new_num = 0 while n: n, r = divmod(n, 10) new_num += r ** 2 return new_num
class Solution:
def isHappy(self, n: int) -> bool:
record = set()
while n not in record:
record.add(n)
new_num = 0
n_str = str(n)
for i in n_str:
new_num+=int(i)**2
if new_num==1: return True
else: n = new_num
return False
class Solution:
def isHappy(self, n: int) -> bool:
seen = set()
while n != 1:
n = sum(int(i) ** 2 for i in str(n))
if n in seen:
return False
seen.add(n)
return True
5 两数之和
题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 2：
输入：nums = [3,3], target = 6
输出：[0,1]
思路
本题需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。因为本题不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。
- 字典法
- 集合法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
records = dict()
for index, value in enumerate(nums):
if target - value in records: # 遍历当前元素，并在map中寻找是否有匹配的key
return [records[target- value], index]
records[value] = index # 如果没找到匹配对，就把访问过的元素和下标加入到map中
return []
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = set() #创建一个集合来存储我们目前看到的数字
for idx, val in enumerate(nums):
if target - val in seen:
return [nums.index(target - val), idx]
seen.add(val)
时间复杂度：O(n)，空间复杂度：O(n)
6 四数相加
题目：给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：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
思路*
本题解题步骤：
- 首先定义一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
- 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
- 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
- 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
dict, cnt = defaultdict(int), 0
for i in nums1:
for j in nums2:
dict[i + j] += 1 # 初始默认是0
for i in nums3:
for j in nums4:
cnt += dict[-(i + j)] # 没有的话就是0
return cnt
时间复杂度：O(n^2)，空间复杂度：O(n^2)
7 赎金信
题目：给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "aab"
输出：true
思路
- defaultdict法
- Counter法*
- count法*
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
dict = defaultdict(int)
for s in magazine:
dict[s] += 1
for s in ransomNote:
dict[s] -= 1
# for val in dict.values():
# if val < 0:
# return False
# return True
return all(val >= 0 for val in dict.values())
from collections import Counter
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
return not Counter(ransomNote) - Counter(magazine)
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
return all(ransomNote.count(c) <= magazine.count(c) for c in set(ransomNote))
8 三数之和*
题目：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
思路
- 哈希法
- 双指针法
去重很容易超时！需要剪枝（有点恶心就跳过吧）
这题双指针法比哈希法高效一点。首先将数组排序，有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() res = [] # res = set() for i in range(len(nums) - 2): left, right = i + 1, len(nums) - 1 # 剪枝 if nums[i] > 0: break elif nums[i] + nums[left] > 0: break if i > 0 and nums[i] == nums[i - 1]: # a去重 continue while left < right: if nums[i] + nums[left] + nums[right] < 0: left += 1 elif nums[i] + nums[left] + nums[right] > 0: right -= 1 else: res.append([nums[i], nums[left], nums[right]]) # 去重逻辑应该放在找到一个三元组之后，对b 和 c去重 while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1# res.add((nums[i], nums[left], nums[right])) left += 1 right -= 1 return res # return list(res)
9 四数之和**(经典
题目：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
思路**
注意细节：不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。
- 双指针法
- 字典法（适用于n数之和题目/要求输出为值*
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() res = [] for i in range(len(nums)): if i > 0 and nums[i] == nums[i - 1]: # a去重 continue if nums[i] > target and nums[i] >= 0: # 剪枝（optional break for j in range(i+1, len(nums)): left, right = j + 1, len(nums) - 1 sum = nums[i] + nums[j] if sum > target and sum >= 0: # 剪枝（optional break if j > i + 1 and nums[j] == nums[j - 1]: # b去重 continue while left < right: if sum + nums[left] + nums[right] < target: left += 1 elif sum + nums[left] + nums[right] > target: right -= 1 else: res.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 -= 1return res
class Solution(object): def fourSum(self, nums, target): # 创建一个字典来存储输入列表中每个数字的频率 freq = defaultdict(int) for i in nums: freq[i] += 1# 创建一个集合来存储最终答案，并遍历4个数字的所有唯一组合 ans = set() for i in range(len(nums)): for j in range(i + 1, len(nums)): for k in range(j + 1, len(nums)): val = target - (nums[i] + nums[j] + nums[k]) if val in freq: # 确保没有重复 count = (nums[i] == val) + (nums[j] == val) + (nums[k] == val) if freq[val] > count: ans.add(tuple(sorted([nums[i], nums[j], nums[k], val]))) return [list(x) for x in ans]