一：哈希表
1、有key:value键值对这样的概念；就是字典；通过key得到value
2、hash碰撞问题：就是key的内存地址相同；使用链表的方法解决
3、字典常见操作
#创建哈希表
hash_tabel={}
#添加元素
hash_tabel['name']='admin'
hash_tabel['age']=25
#删除元素
del hash_tabel['name']
#修改元素
hash_tabel['age']=26
#获取元素
print(hash_tabel['age'])
#判断元素是否存在
if 'name' in hash_tabel:
print('name is in hash_tabel')
else:
print('name is not in hash_tabel')
#获取hash表的长度
print(len(hash_tabel))
#获取hash表的所有键
print(hash_tabel.keys())
#获取hash表的所有值
print(hash_tabel.values())
#获取hash表的所有键值对
for key,value in hash_tabel.items():
print(key,value)
二：刷题
217 存在重复元素
题目：给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false
(1)思路：hash表的思路就是；定义一个地点记录数字出现的次数；如果数字在字典中；对应的value加1；如果没有在里面；纳那么就将对应的value赋值为1；然后判断字典中的值是否存大于等于2；如果是说明数组符合条件；不是最优解！
#方法1 使用哈希表
def func(nums):
hash_table = {}
for i in nums:
if i in hash_table:
hash_table[i]+=1
else:
hash_table[i]=1
if 2 in hash_table.values():
return True
else:
return False
nums = [1,2,3]
print(func(nums))
#方法2 使用集合
def func(nums):
seen = set() # 使用集合来记录遍历过的数字
for num in nums:
if num in seen:
return True# 如果当前数字已经在集合中，说明有重复，返回 True
else:
seen.add(num) # 否则将当前数字添加到集合中
return False # 遍历完整个列表后没有发现重复，返回 False
nums = [1, 5, 2, 3, 4]
result = func(nums)
print(result, end="") # 输出: True
389 找不同
题目：给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
（1）思路：
#方法1 遍历
def func(s,t):
list=[]
for i in t:
if i not in s:
list.append(i)
for i in list:
print(i,end="")
return ""
s=""
t="abcde"
print(func(s,t))
#方法2 将字符串拼接；输出奇数元素def func(s,t):
num=s+t
hash_table={}
for i in num:
if i in hash_table:
hash_table[i]+=1
else:
hash_table[i]=1
for key,value in hash_table.items():
if value==1:
return key
return None
s='abcde'
t='abcdef'
print(func(s,t))
#方法3：使用hash表实现
def func(s,t):
hash_table = {}
for i in s:
hash_table[i] = 1
for i in t:
if i not in hash_table:
return i
return "No different character found"
s = "abcd"
t = "abcd"
print(func(s,t))
496 下一个更大的元素
题目：nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
def func(nums1, nums2):
# 创建哈希表存储 nums2 中每个元素的下一个更大元素
next_greater = {}
stack = []
# 倒序遍历 nums2，构建哈希表
for num in reversed(nums2):
# 保持栈中的元素按从小到大的顺序排列
while stack and stack[-1] <= num:
stack.pop()
# 如果栈不为空，栈顶元素就是 num 的下一个更大元素
if stack:
next_greater[num] = stack[-1]
else:
next_greater[num] = -1
stack.append(num)
# 根据 nums1 构建结果数组
result = []
for num in nums1:
result.append(next_greater[num])
return result
# 测试
nums1 = [2, 4]
nums2 = [1, 2, 3, 4]
print(func(nums1, nums2)) # 输出: [3, -1]