目录
哈希表
什么时候用哈希表呢？快速判断元素是否在集合中，或者元素去重（集合），或者统计重复元素的数量（字典）。
任务
242.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。s 和 t 仅包含小写字母。
思路
使用两个map，key为字符，value为出现次数，比较两个map每个key对应的value是否相同。
- 长度不同一定不同，直接返回False
- 在1不成立的情况下，即长度如果相同时，map2中没有某个map1中的key，返回False
- 在2不成立的情况下，即两者的所有key都相同时，对应的value有不相等的情况，返回False
- 否则返回True
经过学习，知道python中可以直接判断两个字典相等,于是不需要自己写上面的逻辑
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
dic1 = {}
for c in s:
if c not in dic1:
dic1[c] = 1
else:
dic1[c]+=1
dic2 = {}
for c in t:
if not dic2.__contains__(c):
dic2[c] = 1
else:
dic2[c]+=1
# if len(dic1) != len(dic2):
# return False
# for c in dic1:
# if c not in dic2 or dic1[c] != dic2[c]:
# return False
# return True
return dic1 == dic2
另外，可以使用Python collections模块之defaultdict()来避免异常和约束数据类型。
此外以上都是使用了哈希字典的方法，实际此题还可以使用数组作为桶，用下标去作为索引映射26个字母（当前字符-'a'为下标），然后用其值用来表示出现的次数。然后比较两个数组是否相同。更简单地，还可以只用一个数组，统计第一个字符串的时候统计次数用加，第二个的时候用减，然后遍历数组看是否等于0。
349. 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
思路
将两个数组去重，变为两个集合。然后遍历数量小的集合，判断它的每个元素是否在数量大的集合中，如果在，则加入到目标集合（交集）。
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
result = []
set1 = set()
for e in nums1:
set1.add(e)
set2 = set()
for e in nums2:
set2.add(e)
lessSet = set1 if len(set1) <= len(set2) else set2
moreSet = set1 if set2 is lessSet else set2
for e in lessSet:
if e in moreSet:
result.append(e)
return result
实际上用python直接提供了求交集的方法，直接求集合的交集。
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
思路
按快乐数定义，单次循环的步骤如下：
1.每次得到结果后，判断是否是1，如果是1，则返回True，即为快乐数
2.如果还没得到1，判断结果是否在集合中，如果不在，则将其加入到集合中
3.如果在集合中，证明已经陷入无限循环，直接返回False
循环的条件为while(1)
如何得到值，这里是个小重点，即如何分解一个n位数的各位数的值，单次循环的步骤如下：
1.我们采用% 的方式得到当前数字的个位数，
2.采用整数floor除//的方式得到将个位数去除，得到前n-1形成的一个数字
循环条件为n不为0，即至少为1位数。
class Solution:
def isHappy(self, n: int) -> bool:
compareSet = set()
while 1:
n = self.getSum(n)
if n == 1:
return True
if n not in compareSet:
compareSet.add(n)
else:
return False
def getSum(self,n:int) -> int:
sum = 0
while n:
sum += (n%10) *(n%10)
n //=10
return sum
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思路
暴力法很容易想到，就是对每个位置的数，查找其后符合条件的另一个数。
而字典的方法不是很容易想到，这个思路有点像之前的求最短子数组那道滑动窗口，暴力的方法是找当前位置的值和后面哪个位置匹配，后面都是未知的，因此每次都要遍历后面的区间，即使实际上上一蹚已经遍历过了但是没有留下任何有用的信息，因此下次处理时还是要遍历，最终达到O(n^2)的时间复杂度。而优化思路是，确定以当前位置为后面的值，找到它前面哪个值和它匹配，而前面的值又存入到集合/字典这样的数据结构中（记录了信息，让之前的遍历有了意义），方便查找（快速判断元素在集合中），也就是说，只遍历了一遍，前面的值是已知的，或者说是更快得到结果的，因此可以降低时间复杂度。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
result = []
size = len(nums)
for i in range(0,size):
need = target- nums[i]
if need in dic:
result.append(dic[need])
result.append(i)
else:
dic[nums[i]] = i
return result
总结
今天主要的思考如下：
1.哈希表/字典的使用场景，快速判断元素在集合中，以及去重和统计等。
2.python中的 == 与 is
3.处理一个数每个数位上的数
4.对一个问题思考时，可以采用先用暴力法思考，然后优化的思路也许会更容易想到，如之前学到的209. 长度最小的子数组使用滑动窗口解决，以及今天学到的两数之和，都是用这种先暴力然后思考暴力法低效的原因（每一次对后区间的遍历没有给下一次提供有用的信息导致的）从而得到优化的方法（遍历过的节点需要给下一次遍历提供有意义的信息）。