LeetCode 刷题常见技巧
写在前面
最近在 LeetCode 上刷了不少题，慢慢摸索出了一些套路。整理了一份思维导图，把常见的算法技巧都归纳了一下。
算法技巧大纲
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
算法大纲
├── 链表技巧
│ ├── 虚拟头节点（需要返回新链表的时候用）
│ ├── 链表分解
│ └── 快慢指针
│
├── 数组
│ ├── 快慢指针
│ │ ├── 滑动窗口（长短子串问题）
│ │ └── 原地修改类型题目
│ ├── 左右指针
│ │ ├── 二分查找
│ │ ├── N数之和
│ │ ├── 反转数组
│ │ └── 回文判断
│ ├── 前缀和数组（快速计算一个索引区间的和或者积）
│ └── 差分数组（频繁对某个区间加减某个数）
│
├── 队列
│ ├── 先进先出（FIFO）
│ └── 单调队列
│
├── 栈
│ ├── 后进先出（LIFO）
│ └── 单调栈
│
├── 二叉树
│ ├── 深度遍历（三种）：前中后序遍历
│ ├── 广度遍历（三种）：队列辅助、队列+计算深度、队列+路径长度
│ ├── 技巧1（遍历方式）：遍历一遍得到答案
│ └── 技巧2（递归方式）：分解子问题得到答案
│
├── 二叉搜索树
│ └── 二叉搜索树
│
└── 图
├── 二分图判断
├── 并查集
└── 环检测与拓扑排序
一、链表技巧
1.1 虚拟头节点
这个技巧主要用在需要返回新链表的题目中。
核心思想：在原链表前面加一个虚拟节点，这样就不用单独处理头节点的特殊情况了。
适用场景：
- 删除链表节点
- 合并链表
- 需要返回新链表头的题目
📝 例题区域：
1.2 链表分解
有些链表题目需要把链表分成几部分，然后再合并。
核心思想：使用多个虚拟头节点，分别维护不同的子链表。
适用场景：
- 按条件分隔链表
- 奇偶链表
- 重排链表
📝 例题区域：
1.3 快慢指针
快慢指针是链表题的经典技巧，两个指针以不同速度遍历链表。
经典应用：
- 判断链表是否有环
- 找链表的中点
- 找链表倒数第 k 个节点
📝 例题区域：
二、数组技巧
数组是最基础的数据结构，但也有很多巧妙的解法。
2.1 快慢指针
快慢指针不仅在链表中有用，在数组中也很常见。
（1）滑动窗口（长短子串问题）
滑动窗口是处理子串、子数组问题的利器。
核心思想：用两个指针维护一个窗口，右指针扩大窗口，左指针缩小窗口。
适用场景：
- 最长无重复字符子串
- 最小覆盖子串
- 字符串排列
📝 例题区域：
（2）原地修改类型题目
在数组中原地修改，不使用额外空间。
常见题目：
- 移除元素
- 移动零
- 删除排序数组中的重复项
📝 例题区域：
2.2 左右指针
左右指针从数组两端向中间移动，常用于有序数组。
（1）二分查找
二分查找是最经典的左右指针应用。
核心思想：每次排除一半的搜索空间。
📝 例题区域：
（2）N数之和
两数之和、三数之和、四数之和等问题。
核心思想：排序 + 双指针，避免重复。
📝 例题区域：
（3）反转数组
用左右指针交换元素，实现数组反转。
📝 例题区域：
（4）回文判断
判断字符串或数组是否为回文。
📝 例题区域：
2.3 前缀和数组
前缀和是一个非常实用的技巧，可以快速计算子数组的和。
核心思想：preSum[i] 表示前 i 个元素的和，那么 [i, j] 区间的和就是 preSum[j+1] - preSum[i]。
适用场景：
- 快速计算区间和
- 需要频繁查询子数组和的问题
- 和为 K 的子数组
📝 例题区域：
2.4 差分数组
差分数组是前缀和的逆运算，主要用于频繁对某个区间加减某个数的场景。
核心思想：对区间 [i, j] 加上 k，只需要 diff[i] += k, diff[j+1] -= k。
适用场景：
- 区间加法
- 航班预订统计
- 拼车问题
📝 例题区域：
三、队列技巧
队列的特点是先进先出（FIFO），在某些场景下特别好用。
3.1 先进先出（FIFO）
队列的基本特性是先进先出，最先入队的元素最先出队。
核心思想：按照时间顺序处理元素，先到先服务。
适用场景：
- 层序遍历（BFS）
- 任务调度
- 消息队列
- 缓存淘汰（FIFO策略）
📝 例题区域：
3.2 单调队列
单调队列维护一个单调递增或递减的队列，常用于滑动窗口最值问题。
核心思想：队列中保持单调性，队头始终是当前窗口的最值。
经典题目：
- 滑动窗口最大值
- 滑动窗口中位数
📝 例题区域：
四、栈技巧
栈的特点是后进先出（LIFO），很多问题都可以用栈来解决。
4.1 后进先出（LIFO）
栈的基本特性是后进先出，最后入栈的元素最先出栈。
核心思想：处理具有嵌套结构或需要回溯的问题。
适用场景：
- 括号匹配
- 表达式求值
- 函数调用栈
- 深度优先遍历（DFS）
- 撤销操作
📝 例题区域：
4.2 单调栈
单调栈和单调队列类似，维护一个单调的栈。
核心思想：栈中保持单调性，用于找下一个更大/更小的元素。
适用场景：
- 下一个更大元素
- 柱状图中最大的矩形
- 接雨水
- 每日温度
📝 例题区域：
五、二叉树技巧
二叉树是面试的重点，掌握遍历方式是基础。
5.1 深度遍历（三种）
深度优先遍历有三种方式，根据访问根节点的顺序不同而命名。
三种遍历方式：
- 前序遍历：根 → 左 → 右
- 中序遍历：左 → 根 → 右
- 后序遍历：左 → 右 → 根
实现方式：
- 递归实现（简单直观）
- 迭代实现（用栈模拟）
📝 例题区域：
5.2 广度遍历（三种）
广度优先遍历也叫层序遍历，一层一层地遍历。
实现方式：队列辅助、队列+计算深度、队列+路径长度
常见变体：
- 从上到下打印
- 锯齿形层序遍历
- 每层的平均值
📝 例题区域：
5.3 思维方式一：遍历一遍得到答案
遍历一遍得到答案，适合需要访问所有节点的问题。
核心思想：通过一次完整的遍历，在遍历过程中收集信息或执行操作。
适用场景：
- 计算树的最大深度
- 判断是否为平衡二叉树
- 路径总和
- 统计节点数量
📝 例题区域：
5.4 思维方式二：分解子问题得到答案
分解子问题得到答案，利用递归的思想。
核心思想：将问题分解为左右子树的子问题，通过子问题的解构建原问题的解。
适用场景：
- 翻转二叉树
- 合并二叉树
- 对称二叉树
- 构造二叉树
📝 例题区域：
六、二叉搜索树
二叉搜索树（BST）有个重要性质：中序遍历是有序的。
6.1 二叉搜索树
BST 的性质：
- 左子树所有节点的值 < 根节点的值
- 右子树所有节点的值 > 根节点的值
- 左右子树也都是 BST
常见操作：
- 查找：利用 BST 性质，时间复杂度 O(log n)
- 插入：找到合适位置插入
- 删除：需要考虑三种情况
经典题目：
- 验证二叉搜索树
- BST 中第 K 小的元素
- 二叉搜索树的最近公共祖先
📝 例题区域：
七、图技巧
图的题目通常比较复杂，但掌握几个基本算法就能应对大部分题目。
7.1 二分图判断
二分图是指可以将图中的节点分成两个集合，使得所有边都连接不同集合的节点。
判断方法：染色法
核心思想：
- 用两种颜色给节点染色
- 相邻节点必须是不同颜色
- 如果出现冲突，则不是二分图
📝 例题区域：
7.2 并查集
并查集用于处理不相交集合的合并和查询问题。
核心操作：
find(x)：查找 x 的根节点（路径压缩优化）union(x, y)：合并 x 和 y 所在的集合（按秩合并优化）
适用场景：
- 判断图中是否有环
- 朋友圈问题
- 岛屿数量
- 冗余连接
📝 例题区域：
7.3 环检测与拓扑排序
（1）环检测
判断图中是否有环。
方法：
- 有向图：DFS + 记录访问状态（白灰黑三色标记法）
- 无向图：DFS + 记录父节点 或 并查集
📝 例题区域：
（2）拓扑排序
对有向无环图（DAG）进行拓扑排序。
核心思想：
- 找入度为 0 的节点
- 删除该节点及其出边
- 重复上述步骤
实现方式：
- BFS（Kahn 算法）
- DFS（后序遍历的逆序）
应用场景：
- 课程表问题
- 任务调度
📝 例题区域：
写在最后
这些技巧都是我在刷题过程中慢慢总结出来的，每个技巧都会在后续补充更多的例题和详细解析。刷题不是目的，掌握这些思维方式才是关键。
希望这份总结能帮到正在刷题的你！如果有什么问题或者更好的技巧，欢迎交流～
📝 持续更新中…