一、先读题：搞清楚要干什么

1. 确定输入输出

• 输入是什么：数组 / 字符串 / 树 / 图
• 输出是什么：值 / 路径 / 数量 / 是否存在

一句话复述题目：

题目是要求我找……满足……的最优 / 计数结果。

2. 找约束

看关键词：

• n <= 10^5 -> 不能 O(n^2)
• 多组查询 -> 可能要预处理 / 前缀和 / 哈希
• 数据范围很大 -> 可能要 O(n log n)
• 图 / 树 -> 基本 DFS / BFS / DP / 最短路

约束直接决定算法方向。一个常见的误区是忽略输入规模，导致设计出正确但超时的解法。建议在读题后第一时间圈出 n 的范围，以此框定可接受的复杂度上限。

3. 找关键词（”算法信号”）

二、建模：把题变成”数学 / 结构问题”

1. 暴力解法

先写最简单的版本。目的：保证你知道答案是什么样的。这一步不需要考虑效率，只需要确认你对题意的理解是正确的。

2. 反思：暴力为什么慢

• 重复计算？
• 查找太慢？
• 状态太多？

逐一排查这三个维度，通常能定位到瓶颈所在。重复计算指向记忆化，查找慢指向哈希或二分，状态太多则意味着需要剪枝或换模型。

3. 能不能记住结果

• 能 -> DP / memo
• 不能重复扫 -> 前缀和 / 哈希
• 要动态窗口 -> sliding window

三、选模型（核心步骤）

1. 数组 / 字符串类

• 哈希表
• 前缀和
• 双指针
• 滑动窗口

2. 动态最优问题

• DP（状态 + 转移）

反问自己：

我这个问题能不能拆分子问题？

如果子问题之间有重叠，DP 就是首选。如果子问题独立，贪心可能更优。

3. 图 / 树

• DFS（递归）
• BFS（最短路径 / 层级）
• 拓扑排序（依赖关系）

4. 最优 / 极值

• 贪心
• 堆
• 二分答案

当多个模型都看似可行时，优先选择约束最强的那个。例如”有序”+”查找”优先二分，”连续”+”无重复”优先滑动窗口。

四、写代码前必须做的”结构设计”

写代码前，先回答三个问题，答案决定了代码的整体骨架。

1. 状态定义：我需要哪些变量？

算法不是在”写代码”，是在”维护一组状态系统”。用了多少状态变化逻辑，就需要多少变量。变量按职责分为四类：

位置类变量（Pointer / Index）

记录”当前在哪”，控制搜索空间。适用于数组遍历、双指针、滑动窗口、字符串扫描。

状态类变量

记录”当前状态是什么”。例如滑动窗口中的 count（当前窗口里字符频率）、sum（当前窗口和）。

结果类变量

保存”历史最优”，如 ans = 最大值 / 最小值 / 结果集合。特点是不断更新、不参与过程，本质是最终输出缓存。

辅助变量（helper）

临时存储中间状态。

2. 窗口 / 指针含义：每个指针代表什么？

指针的本质是消除重复计算和维护区间。判断标准：这题是不是在处理”位置关系”？例如连续子数组、区间最值/和、有序数组、字符串匹配、去重/覆盖范围。是，则大概率用双指针或滑动窗口。

确定指针数量，本质是确定要维护几个边界：

1 指针（遍历）：只扫描一遍，不需要回头，没有区间。指针 i 从 0 到 n-1。

2 指针（滑动窗口）：需要维护一个区间，区间会动态变化。特征关键词——子数组/子串、连续、最长/最短、满足条件的区间。需要左边界 L 和右边界 R。

2 指针（左右夹逼）：两个序列/对象扫描。特征——两个数组/字符串、有序、求匹配/和/对比。

3 个或以上指针：多状态覆盖。常见于三数问题、区间合并、链表问题（slow / fast / prev）。

3. 哈希含义：我用哈希存什么，为什么？

哈希表的核心作用是 O(1) 的查找和去重。写代码前想清楚三个问题：

• key 是什么？（值、下标、字符、状态）
• value 是什么？（频次、位置索引、是否出现过）
• 为什么需要哈希？如果不用哈希，替代方案是什么（排序后二分、直接数组索引）？

常见的哈希用法：

• 去重：Set 记录已出现元素，如最长无重复子串
• 计数：Map 记录频次，如最小覆盖子串、最多包含 k 种字符
• 索引映射：Map 记录值到最后出现位置的映射，如两数之和

五、最后才是写代码

• 先写框架，再填逻辑
• 变量含义要清晰
• 边界条件单独处理

一个实用的写法顺序：先声明所有变量并注释其含义，再写主循环框架，最后填充内部逻辑。这样能避免写到一半忘记变量用途。

六、验算

写完代码后，按以下顺序验证：

1. 基本用例

用题目给的示例跑一遍，确认输出正确。

2. 边界用例

• 空输入（空数组 / 空字符串）
• 单元素输入
• 全相同元素
• 已排序 / 已逆序
• 最大规模输入（验证是否超时）

3. 极端值

• 负数
• 溢出（Java int 范围）
• 重复值
• 不存在目标值的情况

4. 复杂度复核

回头检查你的解法是否满足第一步约束条件推导出的复杂度要求。如果 n=10^5 但你写了个 O(n^2)，需要重新优化。

5. 手推一轮

选一个中等长度的用例，在纸上或注释中手动模拟循环过程，确保指针移动和状态更新符合预期。这一步能发现大多数逻辑错误。

七、实战口诀

读题 -> 找约束 -> 想暴力 -> 找重复 -> 选模型 -> 定状态 -> 写代码 -> 验证

将这个口诀贴在工位或 IDE 旁，每次做题前默念一遍。熟练后每个步骤只需几秒钟，但能避免大多数方向性错误。

八、一道题实践

题目：最长无重复子串

给定一个字符串 s，找出其中不含重复字符的最长子串长度。

一、第一步：读题 -> 用一句话复述

在一个字符串里，找一段连续区间，这段区间没有重复字符，并且长度最大。

二、第二步：找关键词（决定解法）

看关键词：

• 子串（连续）
• 最长
• 无重复

直接触发一个模型：滑动窗口（双指针）。

三、第三步：暴力解法（必须走这一步）

暴力做法：

1

枚举所有子串 -> 判断是否有重复 -> 取最大

复杂度：O(n^2 * n) = O(n^3)

问题在哪？重复检查”有没有重复字符”。

四、第四步：找优化点（核心）

问：能不能”边走边维护不重复”？

答案：可以。

这时候模型出来了：**用一个窗口维护”当前没有重复字符”**。

五、第五步：确定指针数量

问自己：

• 要不要维护一个区间？要（子串）。
• 这个区间会不会动态变化？会（遇到重复要缩）。

结论：两个指针（L, R）。

六、第六步：确定变量（非常关键）

1）位置变量

1
2

int left = 0;
int right = 0;

控制窗口。

2）状态变量

1

Set<Character> window = new HashSet<>();

当前窗口里有哪些字符。

3）结果变量

1

int maxLen = 0;

记录最大长度。

七、第七步：设计”状态变化逻辑”（最核心）

逻辑一句话版本：右指针扩张窗口，左指针解决冲突。

详细逻辑：

1）右指针往右走：

1

char c = s.charAt(right);

2）如果没有重复 -> 加入窗口：

1

window.add(c);

3）如果有重复 -> 移动左指针：

1
2
3
4

while (window.contains(c)) {
    window.remove(s.charAt(left));
    left++;
}

直到没有重复。

4）更新答案：

1

maxLen = Math.max(maxLen, right - left + 1);

八、第八步：完整 Java 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int lengthOfLongestSubstring(String s) {
    Set<Character> window = new HashSet<>();
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        // 如果有重复，缩小窗口
        while (window.contains(c)) {
            window.remove(s.charAt(left));
            left++;
        }

        // 加入当前字符
        window.add(c);

        // 更新最大长度
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

九、用一个例子手推一遍（非常重要）

字符串：abcabcbb

过程（核心片段）：

1
2
3
4

R=0: a -> [a] -> len=1
R=1: b -> [a,b] -> len=2
R=2: c -> [a,b,c] -> len=3
R=3: a -> 重复！

这时：

1
2

移 L：
[a,b,c] -> [b,c] -> 再加 a -> [b,c,a]

窗口始终保持：无重复。

十、这道题的本质总结

为什么是双指针？因为你在维护一个”动态合法区间”。

为什么需要 Set？因为你需要 O(1) 判断是否重复。

为什么是 while 不是 if？因为可能有多个重复，需要一直缩。

十一、升维理解

这题本质是：维护一个满足条件的最大区间。

这个模型可以复用到：

• 最长子数组（和 <= k）
• 最多包含 k 种字符
• 最小覆盖子串

最后

滑动窗口的本质不是”技巧”，而是”动态维护一个合法区间”。