- 1 Two Sum (Easy)
- 217 Contains Duplicate (Easy)
- 594 Longest Harmonious Subsequence (Easy)
- 128 Longest Consecutive Sequence (Hard)
- 349 两个数组的交集（easy）
- 350 两个数组的交集 II（easy）
- 242 有效的字母异位词（easy）
- 202 快乐数（easy）
- 205 同构字符串（easy）
- 451 根据字符出现频率排序（medium）
- 15 三数之和（medium）
- 18 四数之和（medium）
- 454 四数相加 II（medium）
- 49 字母异位词分组（medium）
- 447 回旋镖的数量（easy）
- 149 直线上最多的点数（hard）
- 219 存在重复元素 II（easy）
- 220 存在重复元素 III（medium）
哈希表的基础知识：
散列表是一种数据结构，其中数据元素的地址或索引值是由散列函数生成的。这使得访问数据的速度更快，因为索引值是数据值的关键字。换句话说，哈希表存储键值对，但密钥是通过哈希函数生成的。
因此，数据元素的搜索和插入函数变得更快，因为键值本身成为存储数据的数组的索引。
在Python中，Dictionary数据类型表示哈希表的实现。以下为根据廖雪峰的资料做的整理：
dic:
- 内置字典：dic的支持，在其他语言中称map，使用键-值（key-value）存储，具有极快的查找度
- 实现方法：给定一个名字，dic在内部就直接计算出名字对应的存放成绩的内存地址，直接取出来
- 存储条件：key-value存储方式：必须根据key算出value的存放位置，取出才能根据key直接拿到Value,可以通过 key放入来把数据放入dict中
- 一个key对应一个value，多次对一个key放入value，后面的值会把前面的值冲掉
- 避免key不存在的错误的两种方法
- 通过in判断key是否存在：
- 通过dict提供的get()方法，如果不存在的话，可以返回None，或者自己指定的value
- 要删除一个key，用pop(key)方法，对应的value也会从dict中删除
- dict内部存放的顺序和key放入的顺序是没有关系的
哈希函数（Hash Function）：将哈希表中元素的关键键值映射为元素存储位置的函数
哈希冲突（Hash Collision）：将不同的关键字通过一个哈希函数可能得到同一个哈希地址
哈希表的核心问题：哈希函数的构建和哈希冲突的解决办法
dict.get() 与 dict[‘key’] 的区别
1.dict[‘key’]只能获取存在的值，如果不存在则触发KeyError
2.dict.get(key, default=None)则如果不存在则返回一个默认值，如果设置了则是设置的，否则就是None
和list比较后，dict的几个特点：
- 查找和插入的速度极快，不会随着key的增加而变慢，但是list相反，时间随元素的增加而增加
- 需要占用大量的内存，内存浪费多，但是list相反，占用空间小，浪费内存很小
- 在需要高速查找的地方无处不在，关键点：dict的key必须是不可变对象：通过key计算位置的算法为哈希算法，要保证算法的正确性，作为key的对象就不能变[字符串–整数等都是不可变的]（hash）,list是可变的，不能作为key
# 附上代码加强理解
# 新建一个字典，存入'名字-成绩'的对照表（无论表多大，查找的速度都不会慢）
d = { 'Michael': 95, 'Bob': 75,'Tracy': 85}
print('d[\'Michael\'] =', d['Michael'])
print('d[\'Bob\'] =', d['Bob'])
print('d[\'Tracy\'] =', d['Tracy'])
# 通过dict提供的get()方法，如果key不存在，返回自己指定的'-1',这里是查看Thomas的成绩是否存在，如果不存在就返回-1
print('d.get(\'Thomas\', -1) =', d.get('Thomas', -1))
# 打印输出结果
# d['Michael'] = 95
# d['Bob'] = 75
# d['Tracy'] = 85
# d.get('Thomas', -1) = -1
set:需要好好的理解，并且要运用好
- 与dict比较的类似，一组key的集合，但不存储value，在set中没有重复的key
- 要创建一个set，需要提供一个list作为输入集合
- 重复元素在set中自动被过滤：
- 通过add(key)方法可以添加元素到set中，可以重复添加，但是没有效果
- 通过remove（key）方法可以删除元素
- set可以看成数学意义上的无序和无重复元素的集合，两个set可以做数学意义上的交集、并集等操作。
- 和dic的唯一区别：没有存储对应的value值
# 附上代码，加强对set的理解
s1 = set([1, 1, 2, 2, 3, 3])
# 重复元素在set中自动被过滤
print(s1)
s2 = set([2, 3, 4])
# 打印s1和s2的交集
print(s1 & s2)
#打印s1和s2的并集
print(s1 | s2)
# 通过add(key)的方法添加4到set中
s1.add(4)
print(s1)
# 通过remove(key)的方法删除s2中的元素
s2.remove(2)
print(s2)
# 输出结果如下：
# {1, 2, 3}
# {2, 3}
# {1, 2, 3, 4}
# {1, 2, 3, 4}
# {3, 4}
通俗理解set和dict背后的哈希表
参考链接：https://blog.csdn.net/weixin_39657125/article/details/111293311
set,dict都是基于哈希表的数据结构
哈希表的实现基于数组和链表
哈希表是重要的数据结构；Python使用它们来实现两种重要的内置数据类型，dict和set（哈希表不是字典，字典和集合这两种数据类型是由哈希表来实现的）
字典是将键映射到值的一般概念。实现这种映射有很多方法，红黑树也可以实现字典
关于python中字典的一些操作
参考链接：
https://www.cjavapy.com/article/934/
https://blog.csdn.net/guifei010/article/details/79165785?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.pc_relevant_default&utm_relevant_index=1
因为字典相对运用的也不少，所以要做一个比较全面的总结，方便后续代码的撰写
创建字典：
- d = {}
- d = dict()
- 导入pytho内置的模块：
访问字典里面的值 - 通过在方括号内引用其键名来访问字典的各项 ：x= d[“name”] 获取key为“name”的值
- 用get()方法来访问:x=d.get(“age”) 获取”age”键的值
改变字典中的值
thisdict = {"name": "cjavapy","age": 3,"gender": "man"}
thisdict["age"] = 5
print(thisdict)
# {"name": "cjavapy","age": 5,"gender": "man"}
遍历字典（用的最多的）
写在前面：遍历字典中这三个是用得非常非常多的，必须要牢记住： keys() 、values() 、items()，分别是返回字典中的所有key、返回字典中的所有值、返回字典中的所有key=value的值（返回的就是一个可以迭代的对象）
- 用for 循环来遍历字典：
# 逐行但打印字典中所有键的名称
thisdict ={'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
for x in thisdict:
#print(x)
value=thisdict[x]
# print("%s:%s"%(x,value))
print("{:}:{:}".format(x,value))
print()
# 输出如下：
# name:XR
# age:28
# gender:man
# address:web
# 逐行打印字典中的所有值
for x in thisdict:
print(thisdict[x])
- 用values()方法来返回字典的值(和上面输出的是相同的)
# vales= thisdict.values() # 这种就是取出了所有的value值了
for x in thisdict.values():
print(x)
- 使用items()来循环遍历键和值
# 这道题是牛客网上的一道题，用的字典来写的，磕磕巴巴的写出来的
hashmap={'rzuwnjvnuz 633': 1, 'atl 637': 1, 'rwyfvzsopsuiqjnr 647': 1, 'eez 648': 1, 'fmwafhhgeyawnool 649': 1, 'c 637': 1, 'f 633': 1, 'ywzqaop 631': 2}
# 循环遍历键和值
for key,value in hashmap.items():
# 注释的写法就是本质，不过这样写太麻烦了
# print(key+ " " +str(value))
print(key,value)
# 输出结果如下：
# rzuwnjvnuz 633 1
# atl 637 1
# rwyfvzsopsuiqjnr 647 1
# eez 648 1
# fmwafhhgeyawnool 649 1
# c 637 1
# f 633 1
# ywzqaop 631 2
判断Key是否存在：
thisdict = {"name": "cjavapy","age": 3,"gender": "man"}
if "name" in thisdict:
print("'name'存在字典中")
# 'name'存在字典中
字典的长度：
主要是为了确定字典中有多少项（键值对）
print(len(thisdict))
向字典中添加项目元素
主要通过新的索引键为其分配值
thisdict = {"name": " XR","age": 28,"gender": "man"}
thisdict["address"] = "web"
print(thisdict)
# {'name': ' XR', 'age': 28, 'gender': 'man', 'address': 'web'}
删除字典中项目元素
- pop()方法移除具有指定key的项:
thisdict ={'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
thisdict.pop("age")
print(thisdict)
# {'name': 'XR', 'gender': 'man', 'address': 'web'}
- popitem()方法删除最后插入的项
thisdict ={'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
thisdict.popitem()
print(thisdict)
# {'name': 'XR', 'age': 28, 'gender': 'man'}
- del()关键字删除具有指定键名的项目
thisdict ={'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
del thisdict["gender"]
print(thisdict)
# {'name': 'XR', 'age': 28, 'address': 'web'}
- clear()方法清空字典
thisdict.clear()
复制一个字典：
不能简单地通过输入dict2 = dict1来复制字典，因为dict2将仅是对dict1的引用，对dict1所做的更改也将自动被改为indict2。
有很多方法可以制作副本，一种方法是使用内置的Dictionary方法copy()。
# 使用copy（）方法制作字典的副本：
thisdict ={'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
mydict=thisdict.copy()
print(mydict)
# 使用内置函数dict()
```python
thisdict ={'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
mydict=dict(thisdict)
print(mydict)
嵌套的字典：
# 构建一个字典，嵌套了三个字典
myfamily = {
"child1" : {"name" : "Emil","year" : 2004},
"child2" : {"name" : "Tobias","year" : 2007},
"child3" : {"name" : "Linus","year" : 2011}
}
通过 sorted函数，可以进行排序（）：**
dict={'A': 1, 'C': 5, 'APP': 4, 'each': 7}
lis1=sorted(dict.items(),key=lambda d:d[0]) #按键来排序
lis2=sorted(dict.items(),key=lambda d:d[1]) #按值来排序
print(lis1)
print(lis2)
# 输出结果
[('A', 1), ('APP', 4), ('C', 5), ('each', 7)]
[('A', 1), ('APP', 4), ('C', 5), ('each', 7)]
d.values() 以列表返回字典中的所有值
hashmap = {8: 46828, 24: 47153, 3: 93735, 13: 72600, 4: 44422}
l=hashmap.values()
print(l)
# dict_values([46828, 47153, 93735, 72600, 44422])
d.keys() 返回列表中所有的键
hashmap = {'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
l=hashmap.keys()
print(l)
# 输出结果
# dict_keys(['name', 'age', 'gender', 'address'])
d.items() 以列表的形式返回可遍历的元组数组
hashmap = {'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
l=hashmap.items()
print(l)
# dict_items([('name', 'XR'), ('age', 28), ('gender', 'man'), ('address', 'web')])
用dict.get()返回指定键的值
语法如下：dict.get(key[,value])
- key–字典中要查的键
- value—如果指定的键值存在，返回默认值
# 辅助理解这个知识点
hashmap = {'name': 'XR', 'age': 28, 'gender': 'man', 'address': 'web'}
# 直接查询
print(hashmap.get('name'))
# 直接查询，查询不成功返回None
print(hashmap.get('birth'))
# 直接查询，查询不成功返回指定的输出
print(hashmap.get('parent'),'该项信息缺失')
# 打印结果如下
XR
None
None 该项信息缺失
与dict[key]的区别：
- get(key) 方法在 key（键）不在字典中时，可以返回默认值 None 或者设置的默认值。
- dict[key]：在Key不在字典中的时候，会触发KeyError异常
d.fromkeys(seq[,val]) 创建一个新字典 以序列seq中的元素做键 val做字典所有键对应的初始值
nums =[0,2,5,8]
d1=dict.fromkeys(nums, 1)
print(d1)
# 输出结果
# {0: 1, 2: 1, 5: 1, 8: 1}
使用模块里面的字典以及与lambda结合的用法
以一个例子来说明：
需要生成一个字典，对于任意key的查询，value都返回XR
# 第一种实现
from collections import defaultdict
def func1():
return XR
func2=defaultdict(func1)
# 第二种实现：采用与lambda结合的方式（不用这种方式就会忘掉）
# 表示用默认的字典defaultdict,如果没有找到对应的value值，会返回一个默认值
func2=defaultdict(lambda:XR)
用于统计一个字符中各个字符串的数量
这个例子使用字典特别的巧妙，值得自己去整理
t="ABBC"
# hashmap=dict((i,t.count(i)) for i t)
# 换一种好理解的方式
hashmap=dict()
for c in t:
if c not in hashmap:
hashmap[c]=1
else:
hashmap[c]+=1
print(hashmap)
# 打印结果如下：
{'A': 1, 'B': 2, 'C': 1}
以下为leetcoad上的一些关于哈希表的比较典型的几道题目，需要重点掌握。
leetcoad01-两数之和
这是leetcoad上一道比较简单的题目，也是第一题，解法一用到了常规的思路，解法二用到了散列表也即哈希表的知识点
解题思路如下：
* 定义一个二维数组（为了存储找到的两个数）
* 写一个两层的循环，范围是0~num.size
* 判断如下：如果下标为i和j的两个数之和等于目标值并且下标不相等
* 把下标为i和j的两个数储存在定义的数组a里面去。
* 循环结束将a输出来
解法一：
class Solution :
def twoSum(self, nums: List[int], target: int) -> List[int]:
list = [0,0] #定义一个二维的数组
#写两层循环直接进行遍历寻找到符合相应条件的值
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j] == target and i != j:
#把相应的符合条件的下标赋值给之前定义的数组
list[0]=i
list[1]=j
return list
解法二：
# 本质上将数组的值和索引存入map中，当遍历到某个值num的时候，判断map中是否含有target-x
class Solution:
'''
two sum的做法，实际就是在nums[i+1:],求解target为-nums[i]的two sum
'''
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 首先构建一个哈希表，用来存放数组的元素值以及索引值
# 其中 key 是数组中的元素值
# value 为数组中元素值的索引
map = dict()
# 接下来，遍历整个数组，利用enumerate函数可以输出下标以及对应的值
for i, num in enumerate(nums):
# 另外的一个值用目标值-num
anotherNum = target - num
# 查看这个值是否在哈希表中
if anotherNum in map :
# 因为题目的意思答案是唯一额，如果有就可以直接输出来，返回两个数的下标
return [ map[ target - num ] , i ]
else:
# 按照nums[i] :i的格式添加到res中，key是对应的值，value是对应的下标
map[nums[i]] = i
return []
leetcoad15-三数之和
leetcoad链接：https://leetcode-cn.com/problems/3sum/
视频链接：https://www.algomooc.com/1287.html
难点分析：如何去除重复解的问题(这道题也是一个关键的题目。务必要牢牢的掌握里面的框架以及实现的细节)
算法流程：排序+双指针
不重复的本质：（用排序就可以解决）
- 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素
- 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素
对于每一重循环 :相邻两次枚举的元素不能相同，也需要剔除掉，跳到下一个不相同的元素
基于三重循环的伪代码实现：
nums.sort()
for first = 0 .. n-1
// 只有和上一次枚举的元素不相同，我们才会进行枚举
if first == 0 or nums[first] != nums[first-1] then
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
for third = second+1 .. n-1
if third == second+1 or nums[third] != nums[third-1] then
// 判断是否有 a+b+c==0
check(first, second, third)
由于固定一个a，那么另外的b和c是联动的，也即第二重循环和第三重循环是并列的关系，继续优化，保持第二重循环不变，将第三重循环变成从数组的最右端开始向左移动的指针
伪代码实现如下：
nums.sort()
for first = 0 .. n-1
if first == 0 or nums[first] != nums[first-1] then
// 第三重循环对应的指针
third = n-1
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
// 向左移动指针，直到 a+b+c 不大于 0
while nums[first]+nums[second]+nums[third] > 0
third = third-1
// 判断是否有 a+b+c==0
check(first, second, third)
流程如下：
- 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
- 对数组进行排序。
- 遍历排序后数组：
- 如果发现nums[i]>0，那么三数之和一定>0,直接退出相应的循环
- 由于不能包含重复的元素，执行一个去重的操作
- left 为从i到 len-1的元素，向右移动，right为从len -1向左移动到i的元素，向左移动，当left <right的时候执行循环
- sum =0，判断左边和右边是否和下一位置重复，去除重复解，然后将左右指针移到下一个位置，寻找新的解
- sum >0,right向左移动
- sum <0,left向右移动
复杂度分析
时间复杂度：O(n2),数组排序O(NlogN),遍历数组O(n),双指针遍历O(n),总体上来说：O(NlogN)+O(n) *O(n)
空间复杂度：O(1)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
#题目存在多组解，每一组解都是一个数组，使用二维数组才存储所有的解
ans = []
#获取数组的长度
n = len(nums)
#边界情况的判断
if nums == None or n <3:
return ans
#对数组进行排序
nums.sort()
#开始遍历整个数组
#在遍历的过程中，观察设置的三个位置的元素之和的大小
#nums[i]为从左到右观察过去的元素
#left 为从i到 len-1的元素
#right为从len -1向左移动到i的元素
for i in range(0,n):
#如果发现nums[i]>0，那么三数之和一定>0,直接退出相应的循环
if nums[i] >0:
break
#由于不能包含重复的元素，执行一个去重的操作
#为了不产生越界的情况，需要注明i的范围是>0的
if i >0 and nums[i] == nums[i -1]:
continue
#left 为从i到 len-1的元素，向右移动
left = i + 1
#right为从len -1向左移动到i的元素，向左移动
right = n - 1
while left < right:
#计算这三者之和
sum = nums[i] +nums[left] +nums[right]
#发现三者之和为0
if sum ==0:
#把相应的结果记录下来
ans.append([nums[i],nums[left],nums[right]])
while left < right and nums[left] == nums[left + 1]:
#left向右移动
left +=1
while left < right and nums[right] == nums[right -1]:
right -=1
# 当上述的情况满足要求的时候，这个时候两个指针需要同时移动才能满足下一次的搜寻要求
#left向右移动
left +=1
#right向左移动
right -=1
#如果三者之和<0,那么需要去寻找一个更大的数出来
elif sum < 0:
#left向右移动
left +=1
elif sum >0:
#right向左移动
right -=1
#返回结果
return ans
如果采用哈希表又应该怎么去做
https://leetcode-cn.com/problems/3sum/solution/you-qian-ru-shen-di-jin-si-jie-fa-jiao-w-sm3j/
https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-xiao-bai-ye-neng-dong-d-ngdl/后面有时间看看这两篇题解，也是写得不错的
# 借鉴别人的思路补充一个哈希+双层循环的思路（两数之和+一次哈希）
# 自定义一个target=-nums[i]，遍历剩下的元素，使用HashSet来寻找是否满足b +c=-a的结果
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 判断边界条件
n= len(nums)
if not nums or n<3: return []
# 创建哈希set集合
res = set()
# 对数组进行排序
nums.sort()
# 如果最小的数大于0或最大的数是小于0的，都说明是不符合要求的
if nums[0]>0 or nums[-1]<0: return []
# 遍历数组
for i in range(n-2):
# 三元组a去重，如果发现后一个数和前一个数相等，执行下一次循环
if i >0 and nums[i]==nums[i-1]: continue
# 一旦发现nums[i]大于0，因为数组时经过排序的，所有不可能有三个数之和等于0，直接跳出循环
if nums[i]>0: break
# 将问题转换为两数之和的问题，创建一个目标值：target=-nums[i]，这里的思路和两数之和如出一辙，也是值得反复回味的。
target=-nums[i]
# 创建一个哈希集合
HashSet=set()
# j从i的下一个数开始遍历,为了寻找第三个数
for j in range(i+1,n):
# 要想凑成0，就要满足第三数=target-nums[j]
anotheNumber=target-nums[j]
# 如果b的值不在在哈希表中，就把b的值加入到哈希表中，然后开始下一轮循环
if anotheNumber not in HashSet:
HashSet.add(nums[j])
continue
# 形成一个三元数组：[a,b,c]
temp = [nums[i],anotheNumber,nums[j]]
# 对这个三元数组再次排序
temp.sort()
# 把这个三元数组转化为元组(去重)，如果不在res数组中，就把这个三元数组以元组的形式加入res中
if tuple(temp) not in res:
res.add(tuple(temp))
# 把res中的元组数据转化为列表后输出最后的结果（列表生成式的写法)
return [list(num) for num in res ]
# 头文件
if __name__ == '__main__':
nums=[-2,0,3,-1,4,0,3,4,1,1,1,-3,-5,4,0]
res = Solution().threeSum(nums)
print("输出 => " ,res)
leetcoad349-两个数组的交集(easy)
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 考虑边界条件：如果两个数组都是空
if not nums1 and not nums2:
return []
# 考虑采用哈希表来解题,构建两个set集合
map1=set(nums1)
print(map1)
map2=set(nums2)
print(map2)
# 创建一个结果数组，用来存储交集元素
res=[]
# 在map1中查找
for num in map1:
# 看查找的值是否在map2中存在
if num in map2:
# 如果存在，就把这个数加入到结果数组中
res.append(num)
return res
leetcoad350-两个数组的交集II(easy)
大体思路：由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
- 首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数
- 遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字且计数为正，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
# 自己第一次写的代码
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 考虑边界条件：如果两个数组都是空
if not nums1 and not nums2:
return []
# 考虑采用哈希表来解题,构建两个set集合
map1=set(nums1)
map2=set(nums2)
# print(map2)
# 创建一个结果数组，用来存储交集元素
res=[]
# 在map1中查找
for num in map1:
# 看查找的值是否在map2中存在
if num in map2:
# 如果存在，统计在两个数组中出现这个数字的次数，取一个较小值
# 不断的循环加入res数组中
a = min(nums1.count(num),nums2.count(num))
for i in range(a):
res.append(num)
return res
看了别人写的做一点优化
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
if not nums1 or not nums2: return []
# 利用dict里面的fromkesc创建哈希表，其中key值设置为0
hashmap1 = dict.fromkeys(nums1, 0)
hashmap2 = dict.fromkeys(nums2, 0)
# 通过for循环不断的计数，最后更新哈希表值为：元素：元素的个数
for num in nums1:
hashmap1[num] += 1
# 查看map1中的元素是否在map2中出现
for num in nums2:
# 如果num在1中的次数大于0进行进行循环
# 这样的好处，无论交集元素是在nums1中多还是在nums2中多，都可以找到比较小的那个值
# 如果是nums1中多，跳出的是for num in nums2，找到最小的交集个数
# 如果是nums2中多，跳出的是if hashmap1[num]>0，找到最小的交集个数
if hashmap1.get(num) and hashmap1[num]>0:
# 在mp2中把该key值的计数+1
hashmap2[num] += 1
# 在map1中把该key值的计数-1
hashmap1[num] -= 1
# print(hashmap2)
res = []
# 这里采用item函数，items() 方法的遍历：items() 方法把字典中每对 key 和 value 组成一个元组，并把这些元组放在列表中返回。
# k是需要加入结果数组的元素，v是需要加入的次数
for k, v in hashmap2.items():
for _ in range(v):
res.append(k)
return res
牛客网上的三道题也是值得整理的：
数组中出现次数超过一半的数字
做题链接：
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=295&tqId=23271&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
自己在提交的时候采用了两种方法：
方法一：采用哈希表法
用哈希表快速统计每一个元素出现的次数，然后将次数出现超过数组长度一半的数挑选出来
class Solution:
def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
# write code here
# 使用字典进行搜索
# 建立一个哈希集合,里面存放每个数字出现的次数
hashmap=dict()
# 数组长度
n = len(numbers)
# 边界情况的处理
# 题目说数组非空，且保证有解，这种情况排除
# if not nums:
# return None
# 如果数组只有一个，那么这个数就是
if n==1:
return numbers[0]
# 让num在nums种遍历
for num in numbers:
# 如果不在哈希表种，就把这个数加进去,并且将num的初始化为1
if num not in hashmap:
hashmap[num]=1
# 如果num已经在哈希表中了，就把对应的值在原来的基础上+1
else:
hashmap[num] +=1
# 是否存在元素出现的次数超过数组长度的一半
if hashmap[num] >n/2:
return num
代码还能做点简化，一步到位，不适合现在的自己
# 全当作学习来看待
class Solution:
def majorityElement(self, nums: List[int]) -> int:
counts = collections.Counter(nums)
return max(counts.keys(), key=counts.get)
方法二：采用Boyer-Moore 投票算法(也是吴师兄课上用到的方法)
# 这种方法也值得自己去深入的思考（有时间的话）
class Solution:
def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
count = 0
candidate = 0
# 在给定的数组中进行遍历
for num in numbers:
if count==0:
# 假设当前的众数为num
candidate=num
# 遍历到的数字与存放的数字相同
if num==candidate:
# 计数+1
count +=1
else:
count -=1
return candidate
数组中只出现一次的两个数字
# 采用的哈希列表的方式，找出出现次数为2的元素，然后按照升序输出即可
class Solution:
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
# write code here
# 创建一个二维数组，用于存放结果
res=[]
count = 0
# 创建一个set集合
hashmap=dict()
# 开始统计元素出现的频率
for num in array:
if num not in hashmap:
hashmap[num]=1
else:
hashmap[num] +=1
for i in array:
if hashmap[i]==1:
res.append(i)
return sorted(res)
缺失的一个正整数（leetcoad41同题型）
# 总体思路，用哈希表把nums中的元素记录下来，然后看1-n中是否有元素在这个哈希表中，如果没有找到，把数加入到结果数组中，那么这个结果数组中最小的值就是没有找到的就是缺失的第一个正整数，如果都找了，这里我判断的是res数组为空，此时丢失的数就是n+1这个数
class Solution:
def minNumberDisappeared(self , nums: List[int]) -> int:
# write code here
# 先找到没有出现的元素
# 然后取出没有出现的元素的最小值
n = len(nums)
res=[]
# 构建一个哈希表存放nums中原本有的数
hashmap ={num for num in nums}
for i in range(1,n+1):
# 如果在哈希表中没有这个数，说明缺失的数就是这个数
if i not in hashmap:
res.append(i)
# 如果1-n都存在这个数，那么说明这个数是n+1
else:
continue
# 对结果数组进行判断，如果为空，说明1-n在nums中都有，直接返回n+1
if not res:
return n+1
return min(res)
在leetcoad上针对这道题还有很多其他的解法，有时间也可以自己仔细地看看，研究研究。
https://leetcode-cn.com/problems/first-missing-positive/