一、哈希
哈希表（散列表）：一种通过键值对映射来高效存储和查找数据的数据结构
核心思想是用一个哈希函数，把键（Key）转换成一个数组索引，可以直接通过索引定位到对应的值，从而实现O（1）时间复杂度的增删改查。
哈希表特性：高效读写、基于哈希函数映射、处理哈希冲突的方法（键地址法、开放寻址法）、空间换时间、无序性
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
-
用字典存储值和对应的索引
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 用字典存储值和对应的索引
num_map={}
for index,num in enumerate(nums): # enumerate() python中内置函数，用来给可迭代对象的每个元素配上一个索引
# 计算当前值需要的补数
x=target-num
if x in num_map:
# 找到补数，返回之前的索引和当前索引
return [num_map[x],index]
# 没找到就把当前值和索引存入字典
num_map[num]=index
2.字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表
-
生成特征键：给一组内容相似但形式不同的元素，找一个唯一的共同标识，通过这个表示把它们快速分到同一组里
-
生成特征键的方法:排序法、计数法
-
排序法 key=''.join(sorted(x))
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
list1={}
for x in strs:
# 生成特征键：给一组内容相似但形式不同的元素，找一个唯一的共同标识，通过这个表示把它们快速分到同一组里
# 生成特征键的方法:排序法、计数法
key=''.join(sorted(x))
# 如果键不存在，就创建一个空列表
if key not in list1:
list1[key]=[]
# 把当前字符串添加到对应键的列表里
list1[key].append(x)
return list(list1.values())
3.最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
1.先把数组转集合，去重
2.遍历集合中的每个数字num，只有当num-1不存在时，才能说明num是起点
3.从起点开始，找num+1 num+2…，并记录序列长度
4.维护最长长度，每次比较时更新
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 1.数组转集合
num_set=set(nums)
max_length=0
for num in num_set:
# 当num-1不存在时，num才是起点
if num-1 not in num_set:
current_num=num
current_length=1
# 向后查找连续数字
while current_num+1 in num_set:
current_num+=1
current_length+=1
# 更新最大长度
if current_length>max_length:
max_length=current_length
return max_length
二、双指针
双指针：在数据结构（通常是数组/链表）上使用两个指针来协同移动
本质是通过两个指针的移动来减少重复计算，两个指针可以同向移动，也可以相向移动
快慢指针（同向双指针）[判断链表是否有环、寻找链表中间节点、删除数组中的重复项]、
左右指针（相向双指针）[两数之和、反转数组、回文字符串判断、盛水最多的容器]、
滑动窗口（同向双指针的一种变形）[最长无重复子串、最小覆盖子串、子数组的最大和]
双指针特性：时间效率高、空间复杂度低、使用场景明确（适合处理有序数组/b链表、区间类问题和需要减少重复计算的场景）
1.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
双指针：
1.慢指针：记录下一个非零元素应该放置的位置；
2.快指针：遍历整个数组，寻找非零元素
3.快指针遇到非零元素时，就将它和慢指针位置的元素交换，然后慢指针右移
4.遍历结束后，慢指针之后的位置全部补0
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
slow=0
# 1.所有非0 元素前移
for fast in range(len(nums)):
if nums[fast]!=0:
nums[slow]=nums[fast]
slow+=1
# 2.把后面位置补0 rang(slow,len(nums)) 生成一个从slow开始，到数组末尾的整数序列
for x in range(slow,len(nums)):
nums[x]=0
return nums
2.盛水最多的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])
双指针
1.初始指针：左指针left放在数组开头，右指针right放在数组末尾
2.计算面积 min(height[left],height[right])*(right-left)决定 –面积由最短的那条线决定
3.移动指针，移动高度最小的那个指针
4.更新最大面积
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
left=0
right=len(height)-1
max_area=0
while left<right:
# 计算当前面积
current_area=min(height[left],height[right])*(right-left)
# 更新最大面积
if current_area>max_area:
max_area=current_area
# 移动短指针
if height[left]<height[right]:
left+=1
else:
right-=1
return max_area
3.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
排序+双指针
1.排序预处理：先对数组排序，方便后续去重和双指针排序
2.固定第一个数：遍历数组，每次固定一个数nums[i]作为三元组的第一个数
3.双指针找另外两个数：在i右侧的子数组中，用左右指针寻找和为-num[i]的两个数
4.去重处理：如果当前数和前一个数相同，跳过避免重复；找到符合条件的术后，移动指针并跳过重复值
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# 1.排序 –方便后续操作
nums.sort()
result=[]
n=len(nums)
for i in range(n): # 遍历索引，间接访问元素
# 排序之后（升序），如果第一个数就>0 后面肯定更大，不可能3数相加为0 跳过
if nums[i]>0:
break
# 跳过重复的第一个数
if i>0 and nums[i]==nums[i-1]:
continue
left=i+1
right=n-1
target=-nums[i]
while left<right:
current_num=nums[left]+nums[right]
if current_num==target:
# 将三元组添加到数组中
result.append([nums[i],nums[left],nums[right]])
# 跳过left重复值
while left<right and nums[left]==nums[left+1]:
left+=1
# 跳过right重复值
while left<right and nums[right]==nums[right-1]:
right-=1
# 找到结果 同时移动双指针
left+=1
right-=1
elif current_num<target:
left+=1
else:
right-=1
return result
