LeetCode 刷题方法与 Java 解题模板

S2-008建议学进阶约 60 分钟JDK 21计算机基础 · 数据结构与算法

1. 本节定位

《时间复杂度和空间复杂度》讲了复杂度分析；本节讲**"怎么在有限时间里把题做对"**：

text

刷题的目标不是"做过 500 题"，而是"看到新题能判断它属于哪类、该用什么套路"  ✓✓

本节的四个模板覆盖了面试里最高频的一批题 ✓ ——它们是"信号 → 套路"的映射表 ✓

2. 学习目标

掌握四个高频模板（双指针 / 滑动窗口 / 二分 / BFS-DFS）★★★；
会判断"听到什么信号该用哪个模板" ★★★；
知道二分查找的两个边界变体怎么写 ★★★；
知道 BFS 与 DFS 各自的适用场景 ★★★；
掌握"从暴力解到最优解"的推导路径 ★★。

3. 前置知识检查

掌握数组、哈希表、队列的基本操作吗？（《数据结构：数组、链表、栈与队列》、《树、堆与哈希表》）✓
会分析复杂度吗？（《时间复杂度和空间复杂度》）✓

4. 为什么需要这个知识

先看一个刷题的常见困境 ✗：

text

"刷了 200 题，遇到新题还是不会"        ← 原因：记的是"答案"，不是"信号"

★ 本节的写法是"从信号反推套路" ✓✓：

题面出现什么	该想到什么
"有序数组" + "找两个数" ★★	双指针 ✓
"连续子数组/子串" + "最长/最短" ★★★	滑动窗口 ✓
"有序" + "查找 / 第一个满足条件" ★★★	二分 ✓
"最短路径"（无权图） ★★	BFS ✓
"所有方案 / 全排列 / 连通块" ★★	DFS + 回溯 ✓
"第 k 个 / Top K" ★★	堆（《树、堆与哈希表》）✓

★ 刷题的正确姿势 ✓：

text

① 先写暴力解（保证思路对、能过样例）
② 找出暴力解里的"重复扫描"或"重复计算"
③ 用模板消除它
④ 记录"信号 → 模板"这个映射（这才是可迁移的能力）✓✓

5. 核心概念

5.1 模板一：双指针 ★★★

适用信号：数组有序，且需要"两个位置配合"（两数之和、三数之和、反转、去重）✓

java

int lo = 0, hi = n - 1;
while (lo < hi) {
    int sum = a[lo] + a[hi];
    if (sum == target) { return new int[]{lo, hi}; }
    if (sum < target) { lo++; } else { hi--; }
}

★ 为什么它是 O(n) ✓：

每一步都排除了一整行或一整列的组合 ✓
暴力是 O(n²)（每对都试），双指针只走一遍 ✓✓

★ 本节的实测（LeetCodeLesson）：

text

数组：[1, 3, 5, 7, 9, 11, 13, 15]，目标：20
结果下标：[2, 7]（值 5 + 15）✓

n=20000 找两数之和：暴力 若干十毫秒 | 双指针 1 ms 级别

★ 一个重要限制 ✗：双指针要求"有序" ✓ ——无序时要先排序（O(n log n)）或改用哈希表（O(n) 空间） ✓

5.2 模板二：滑动窗口 ★★★

适用信号："连续子数组/子串" + "满足某条件的最长/最短/计数" ✓✓

java

Map<Character, Integer> lastIndex = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < n; right++) {
    char c = s.charAt(right);
    Integer last = lastIndex.get(c);
    if (last != null && last >= left) {
        left = last + 1;              // ★ 左边界只前进，不回退
    }
    lastIndex.put(c, right);
    best = Math.max(best, right - left + 1);
}

★★ 关键约束：left 只增不减 ✓✓ ——这是窗口能做到 O(n) 的根本原因 ✓

★ 如果 left 可能回退 ✗ → 就退化成 O(n²) ✓

★ 滑动窗口的通用骨架 ✓：

步骤	说明
① 右指针扩张	把新元素纳入窗口 ✓
② 判断"不合法"	如出现重复字符 ✓
③ 左指针收缩	直到窗口重新合法 ✓
④ 更新答案	在合法状态下记录最优 ✓

★ 什么时候"收缩"是这段代码最容易写错的地方 ⚠️：

有的是"while 收缩到合法"，有的是"if 只收缩一步" ✓
判断依据：窗口大小是"必须维持"还是"可以更大" ✓

5.3 模板三：二分查找 ★★★

适用信号："有序" + "查找 / 第一个满足条件的位置" ✓

★ 两个必须记住的变体 ✓✓：

java

// ① lower bound：第一个 >= target 的位置
static int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;              // ★ 区间是 [lo, hi)
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;          // ★ 位运算防溢出
        if (a[mid] < target) { lo = mid + 1; } else { hi = mid; }
    }
    return lo;                              // ★ 返回 lo
}

// ② upper bound：第一个 > target 的位置（减一就是"最后一个 <= target"）
static int upperBound(int[] a, int target) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] <= target) { lo = mid + 1; } else { hi = mid; }
    }
    return lo;
}

★ 避开死循环的三个要点 ✓✓：

#	要点
①	统一用 `while (lo < hi)` + 区间 `[lo, hi)` ✓
②	`mid = (lo + hi) >>> 1`（不要用 `(lo + hi) / 2`：两数相加可能溢出）✗
③	每一轮都要让边界真的收缩（`lo = mid + 1` 或 `hi = mid`）✓

★ 第三条最容易被忽略 ✗：

java

if (a[mid] < target) { lo = mid; }        // ✗ 死循环！lo 可能不再前进

★ 实用建议 ✓：如果只是"查有没有"，直接用 Arrays.binarySearch ✓ 只有需要"边界语义"时才手写 ✓✓

5.4 模板四：BFS 与 DFS ★★★

适用信号：

需求	选	原因
无权图最短路径 ★★	BFS ✓✓	按层扩展，首次到达即最短 ✓
层序遍历	BFS ✓	天然按层 ✓
判断连通性 / 遍历所有路径	DFS ✓	代码短、回溯自然 ✓
找所有解（排列、组合、划分） ★★	DFS + 回溯 ✓✓	便于剪枝与状态回退 ✓
深度可能很大	BFS 或迭代 DFS ✓	避免递归栈溢出（《递归、分治与动态规划》）✓

★ 一句话："求最短用 BFS，求所有解用 DFS" ✓✓

BFS 的骨架 ✓：

java

Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
    int node = queue.poll();
    for (int next : neighbors(node)) {
        if (visited.add(next)) {              // ★ add 返回 false 说明访问过
            queue.add(next);
        }
    }
}

★★ visited 是必需的 ✓✓ ——不加它，带环图会死循环 ✗✗

★ 一个易错点 ⚠️：

visited.add(next) 必须在"入队时"做，不能在"出队时"做 ✓✓
否则同一个节点可能被多次入队 ✗（导致重复计算或超时）✓

5.5 从暴力到最优的四步推导 ★★

以一个具体例子说明（"找数组里两数之和等于目标值"）：

text

① 暴力：两层循环，每对都试                      O(n²)  ✗
② 观察：内层在"找一个特定值的数"                → 这是"查找"问题
③ 换结构：把"看过的数"放进 HashSet              O(n) 时间 + O(n) 空间  ✓
④ 再想：如果数组有序，能不能 O(1) 空间？        → 双指针                O(n) 时间 + O(1) 空间 ✓✓

★ 这个推导过程就是"刷题的产出" ✓✓：

不是"这题我做过"，而是"我知道它会往哪个方向优化" ✓

★ 本节的实测（LeetCodeLesson 的对照实验）：

text

n=20000 找两数之和：暴力（O(n²)）需要几十毫秒 | 双指针（O(n)）只需 1 ms 级

★ 差距的规模感 ✓：

n	暴力 O(n²)	双指针 O(n)
2 万	几十 ms	< 1 ms ✓
100 万	几分钟 ✗✗	几十 ms ✓

★ 所以"模板"的价值不是"代码短"，而是"把不可用变成可用" ✓✓

6. 递进示例

6.1 最小示例：三数之和

text

① 排序
② 枚举第一个数 i
③ 对剩下的区间做"两数之和"（双指针）
④ 跳过重复元素去重

6.2 业务示例：无重复最长子串

见 5.2 ✓

6.3 反例：用暴力解通过大数据

能过样例，但过不了隐藏用例 ✗（这就是 LeetCode 会"超时"的原因）✓

7. 完整可运行代码与实测

代码：labs/cs-basics/src/main/java/cn/kb/learn/cs/LeetCodeLesson.java

运行：

powershell

cd labs
.\mvnw.cmd -pl cs-basics compile
java "-Dstdout.encoding=UTF-8" -cp cs-basics/target/classes cn.kb.learn.cs.LeetCodeLesson

实测输出（节选）：

text

===== 模板一：双指针（有序数组两数之和）=====
  数组：[1, 3, 5, 7, 9, 11, 13, 15]，目标：20
  结果下标：[2, 7]（值 5 + 15）✓

===== 模板四：BFS 与 DFS 怎么选 =====
  图：0->{1,2}, 1->{3}, 2->{3,4}, 3->{5}, 4->{5}
  0 到 5 的最短距离：2 ✓

===== 实测：模板解法值多少时间 =====
  n=20000 找两数之和：暴力 若干十毫秒 | 双指针 1 ms 级别

★ 三条可落地的结论 ✓：

#	结论
①	看到"有序 + 找数"就想双指针或二分 ✓
②	看到"连续子串/子数组 + 最长最短"就想滑动窗口 ✓
③	看到"最短路径（无权）"就想 BFS，"所有方案"就想 DFS + 回溯 ✓

8. Debug 观察点

把双指针版换成两层循环：观察 n=2 万时的耗时差异 ★★；
把滑动窗口的 left = last + 1 改成 left++：观察答案变小 ✗（窗口不合法）★；
把二分的 lo = mid + 1 改成 lo = mid：观察死循环 ✗✗；
把 BFS 的 visited 去掉：观察带环图的死循环 ✗✗；
把 visited.add 从"入队时"挪到"出队时"：观察节点被重复入队 ⚠️。

9. 常见错误

#	错误	说明
1	二分用 `lo = mid` 导致死循环 ✗✗	边界没收缩（5.3）✗✗
2	二分用 `(lo + hi) / 2` ✗	可能溢出成负数 ✓
3	滑动窗口的 `left` 会回退 ✗	退化成 O(n²) ✓
4	BFS 忘了 `visited` ✗✗	带环图死循环 ✓
5	`visited` 在出队时才标记 ✗	节点被重复入队 ✓
6	双指针用在无序数组上 ✗✗	结论错误 ✓
7	只背答案不记"信号 → 套路" ✗✗	遇到新题还是不会 ✓

10. 动手实验

目标：把"信号 → 模板"变成本能。

步骤：

跑 LeetCodeLesson，确认四个模板的输出 ✓；
给自己出 10 道题（从题解里找），每道题只做一件事：写出"它属于哪类模板、信号是什么" ★★；
挑一道"两数之和"，分别用哈希表与双指针各写一遍，对比空间与前提条件 ✓；
把二分的两个变体都手写一遍，用 {1,2,2,2,3} 与 target=2 验证 ✓；
实现一个"网格最短路径"（BFS），再实现"所有路径"（DFS），感受两者的差别 ★。

验收方式：能对任意一道题说出"它的信号是什么、该用哪个模板"。

扩展任务：建立自己的"模板卡片"：

每个模板一张卡：信号、骨架代码、易错点、例题 ✓；
每做完一题就更新卡片（而不是抄题解）✓；
说明：为什么"卡片法"比"按题号刷"更有效（提示：它建立的是可迁移的映射关系）✓✓

11. 练习题

判断：双指针可以用于任意数组的两数之和。（对 / 错）
填空：二分的两个变体是 ______ 与 ______；返回"第一个 > target 的位置"的是 ______。
简答：为什么滑动窗口的 left 只能前进不能回退？
（代码阅读）

java

while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] < target) { lo = mid; } else { hi = mid; }
}

这段代码有两个 bug，分别是什么？ 5. （编程）用滑动窗口解决"长度最小的子数组"：找出和 ≥ target 的最短连续子数组，返回长度。

参考答案（要点）

错。双指针要求数组有序 ✓ ——无序要先排序或用哈希表 ✓★
lower bound（第一个 ≥ target）；upper bound（第一个 > target）；upper bound ✓
因为 left 回退意味着"重新检查已排除的窗口" ✗ ——复杂度就从 O(n) 变成 O(n²) ✓★
① (lo + hi) / 2 可能溢出 ✗；② lo = mid 会导致死循环（lo 可能不前进）✗✗
要点：右指针扩张累加和，当和 ≥ target 时收缩左指针并更新最小值 ✓ 注意用 while 收缩（可能一次收缩多步） ✓

12. 掌握标准

[ ] 掌握四个模板，并能说出各自的"信号" ★★★；
[ ] 知道二分的两个变体与三个避坑要点 ★★★；
[ ] 知道滑动窗口"左边界不回退"这个核心约束 ★★★；
[ ] 知道 BFS 与 DFS 的选择依据 ★★★；
[ ] 知道 visited 必须"入队/入栈时"标记 ★★；
[ ] 掌握"暴力 → 观察重复 → 换结构"的推导路径 ★★；
[ ] 建立了自己的"模板卡片" ✓。

13. 扩展资源

14. 下一步学习

S2 的算法部分（《数据结构：数组、链表、栈与队列》 ~ 《LeetCode 刷题方法与 Java 解题模板》）到此完成。接下来：

S2-009 操作系统：进程与线程（下一批）
之后是网络五节（《网络分层模型与数据传输过程》 ~ 《网络安全基础》）

前置知识

S2-007 时间复杂度和空间复杂度

后续知识

S7-004 算法题准备策略

进度只保存在本机浏览器，可随时清除

外部学习资源

面试题库索引

项目与练手索引

工具与软件索引

LeetCode 刷题方法与 Java 解题模板

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 模板一：双指针 ★★★

5.2 模板二：滑动窗口 ★★★

5.3 模板三：二分查找 ★★★

5.4 模板四：BFS 与 DFS ★★★

5.5 从暴力到最优的四步推导 ★★

6. 递进示例

6.1 最小示例：三数之和

6.2 业务示例：无重复最长子串

6.3 反例：用暴力解通过大数据

7. 完整可运行代码与实测

8. Debug 观察点

9. 常见错误

10. 动手实验

11. 练习题

12. 掌握标准

13. 扩展资源

14. 下一步学习

前置知识

后续知识

LeetCode 刷题方法与 Java 解题模板 ​

1. 本节定位 ​

2. 学习目标 ​

3. 前置知识检查 ​

4. 为什么需要这个知识 ​

5. 核心概念 ​

5.1 模板一：双指针 ★★★ ​

5.2 模板二：滑动窗口 ★★★ ​

5.3 模板三：二分查找 ★★★ ​

5.4 模板四：BFS 与 DFS ★★★ ​

5.5 从暴力到最优的四步推导 ★★ ​

6. 递进示例 ​

6.1 最小示例：三数之和 ​

6.2 业务示例：无重复最长子串 ​

6.3 反例：用暴力解通过大数据 ​

7. 完整可运行代码与实测 ​

8. Debug 观察点 ​

9. 常见错误 ​

10. 动手实验 ​

11. 练习题 ​

12. 掌握标准 ​

13. 扩展资源 ​

14. 下一步学习 ​

前置知识

后续知识

LeetCode 刷题方法与 Java 解题模板

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 模板一：双指针 ★★★

5.2 模板二：滑动窗口 ★★★

5.3 模板三：二分查找 ★★★

5.4 模板四：BFS 与 DFS ★★★

5.5 从暴力到最优的四步推导 ★★

6. 递进示例

6.1 最小示例：三数之和

6.2 业务示例：无重复最长子串

6.3 反例：用暴力解通过大数据

7. 完整可运行代码与实测

8. Debug 观察点

9. 常见错误

10. 动手实验

11. 练习题

12. 掌握标准

13. 扩展资源

14. 下一步学习