哈希表理论基础
std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。?
?std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的
总结：unordered_set 和 unordered_map的底层实现都是哈希表，set, multiset, map, multimap, 底层实现都是红黑树。set 的话不能修改，只能增删。 map的话，key都是不能修改的，value可以去修改。使用红黑树实现的结构，都是有序的，并且查找和增删复杂度都是O(logn), 使用哈希表实现的unordered_set/map都是无序的，查询和增删效率都是O(1).
什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候 或者?需要判断一个元素是否出现过，就要考虑哈希法。 这句话很重要，大家在做哈希表题目都要思考这句话。
242.有效的字母异位词
先提供最容易想到的解法，去判断两个dict是否不同：
def isAnagram(self, s: str, t: str) -> bool:
dicta = {}
dictb = {}
for i in s:
dicta[i] = dicta.get(i,0) + 1
for i in t:
dictb[i] = dictb.get(i,0) + 1
return dicta == dictb然后是用数组去记录出现的次数，ord(i) - ord('a'), 总共有26个，正好映射到长度为26的数组的索引
def isAnagram(self, s: str, t: str) -> bool:
record = [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(26):
if record[i] != 0:
return False
return True349.两个数组的交集
遍历， 拿集合去重? ? or? ? 直接求交集然后转化成list出
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
a, res = set(), list()
for i in nums1:
if i in nums2:
a.add(i)
for i in a:
res.append(i)
return resdef intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))202. 快乐数
题目中说了会?无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
判断sum是否重复出现就可以使用unordered_set。
还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。
def isHappy(self, n: int) -> bool:
def cal(num: int) -> int:
sum_ = 0
while num:
sum_ += (num % 10) ** 2
num = num // 10
return sum_
record = set()
while True:
sum = cal(n)
if sum == 1:
return True
if sum in record:
return False
else:
record.add(sum)
n = sum1. 两数之和
在这个题中，我们找两个数之和是否存在，当我们遍历到一个数的时候，我们想知道，target - nums[i], 是否之前遍历到过。这样的话，我们才需要用一个东西去储存之前遍历到的元素的值。
那么为什么要用map, 因为我们需要返回下标，元素值，下标，谁做key, 谁做value呢？我们需要返回的东西，要做value.
那么就是 我们在遍历的时候，要把遍历到的元素的值nums[i], 当做key, 把下标i当做value, 去做一个储存。那么我们在查找的时候，就能很容易的以O(1)的复杂度去查找到是否有 target - nums[i]的存在，并且返回下标
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = {}
for i in range(len(nums)):
if target - nums[i] in hashtable:
return [i,hashtable[target - nums[i]]]
hashtable[nums[i]] = i