哈希表、双指针、滑动窗口、栈、BFS | ：原理 + 解决什么问题 + 怎么实现 + 应用场景

一、哈希表Hash Table / Python 里叫 dict /set1. 原理超级通俗哈希表 字典你给一个key关键词它能瞬间找到 value。它内部用哈希函数把 key 转成一个地址所以查找极快。2. 它解决什么问题快速判断一个元素是否存在快速统计次数快速做映射关系去重时间复杂度O(1)秒杀数组遍历 O (n)3. 怎么实现Pythonpython运行# 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 Pointers1. 原理用两个变量当作指针在数组 / 字符串上一起移动代替多层循环。两种最常用左右指针一头一尾向中间走快慢指针一个走得快一个走得慢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 Window1. 原理双指针的升级版。用left 和 right 维护一个区间窗口right 不断往右扩大left 遇到不满足条件就往右缩像一根尺子在数组上滑动动态找最优区间。2. 解决什么问题解决连续子数组 / 连续子串问题最长无重复子串最短子数组子数组和连续活跃天数3. 怎么实现万能模板python运行left 0 for right in range(len(s)): 把 s[right] 加入窗口 while 窗口不合法: 移除 s[left] left 1 更新最优答案4. 应用场景最长无重复子串子数组和 ≥ target连续用户活跃天数流量统计、时间窗口指标四、栈Stack1. 原理后进先出像桶、弹匣、书堆最后放进去的最先拿出来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一圈圈扩散找最短路径、连通块