哈希表、双指针、滑动窗口、栈、BFS | ：原理 + 解决什么问题 + 怎么实现 + 应用场景
一、哈希表（Hash Table / Python 里叫 dict /set）
1. 原理（超级通俗）
哈希表 =字典你给一个key（关键词），它能瞬间找到 value。它内部用哈希函数把 key 转成一个地址，所以查找极快。
2. 它解决什么问题？
- 快速判断一个元素是否存在
- 快速统计次数
- 快速做映射关系
- 去重
时间复杂度：O(1)秒杀数组遍历 O (n)
3. 怎么实现？（Python）
python
运行
# 1. 字典 dict：存 key-value d = {} d["a"] = 1 # 添加 print(d["a"]) # 查询 if "a" in d: # 判断存在 # 2. 集合 set：只存 key，用于去重 s = set() s.add(1) if 1 in s:4. 应用场景
- 两数之和
- 数组去重
- 词频统计
- 判断重复元素
二、双指针（Two Pointers）
1. 原理
用两个变量当作指针，在数组 / 字符串上一起移动，代替多层循环。
两种最常用：
- 左右指针：一头一尾向中间走
- 快慢指针：一个走得快，一个走得慢
2. 解决什么问题？
把O (n²) 暴力循环 → O (n)极大优化速度！
3. 怎么实现？
① 左右指针（有序数组两数之和）
python
运行
left = 0 right = len(nums) - 1 while left < right: if 满足条件: left += 1 else: right -= 1② 快慢指针（删除重复元素）
python
运行
slow = 0 for fast in range(len(nums)): if nums[slow] != nums[fast]: slow += 1 nums[slow] = nums[fast]4. 应用场景
- 有序数组两数之和
- 数组去重
- 回文字符串
- 链表找中点
三、滑动窗口（Sliding Window）
1. 原理
双指针的升级版。用left 和 right 维护一个区间（窗口）right 不断往右扩大left 遇到不满足条件就往右缩
像一根尺子在数组上滑动，动态找最优区间。
2. 解决什么问题？
解决连续子数组 / 连续子串问题：
- 最长无重复子串
- 最短子数组
- 子数组和
- 连续活跃天数
3. 怎么实现？（万能模板）
python
运行
left = 0 for right in range(len(s)): 把 s[right] 加入窗口 while 窗口不合法: 移除 s[left] left += 1 更新最优答案4. 应用场景
- 最长无重复子串
- 子数组和 ≥ target
- 连续用户活跃天数
- 流量统计、时间窗口指标
四、栈（Stack）
1. 原理
后进先出像：桶、弹匣、书堆最后放进去的，最先拿出来
2. 解决什么问题？
- 括号匹配
- 逆序输出
- 找最近比大小的元素（单调栈）
- 递归逻辑
3. 怎么实现？
python
运行
stack = [] stack.append(x) # 入栈 stack.pop() # 出栈 stack[-1] # 看栈顶4. 应用场景
- 有效括号
- 字符串去重
- 函数调用栈
- 每日温度
五、BFS 广度优先搜索
1. 原理
一圈一圈往外扩散从起点开始，先遍历近的，再遍历远的用队列（queue）实现
2. 解决什么问题？
- 最短路径
- 图遍历
- 网格搜索（岛屿、连通块）
- 层级遍历
3. 怎么实现？
python
运行
from collections import deque q = deque() q.append(start) while q: 取出队首 把上下左右合法的点加入队列4. 应用场景
- 岛屿数量
- 迷宫最短路径
- 层级遍历
- 社交网络关系距离
我再给你一句超级总结（面试必背）
- 哈希表：快速查找、去重、统计
- 双指针：用两个下标优化循环
- 滑动窗口：动态区间，解决连续子串问题
- 栈：后进先出，适合匹配、逆序
- BFS：一圈圈扩散，找最短路径、连通块