图解算法通识讲义经典套路
滑动窗口与动态伸缩模型
核心心智模型：伸缩自如的动态视窗：右边界无脑探路吃进，左边界按需收缩吐出，维护区间不变量。
核心交互式算法图解演练沙盒
滑动窗口模型
无重复字符滑动窗口动态伸缩演练
步骤 1 / 5
当前窗口区间：[0 ... 0]
窗口长度：1
历史最大长度 maxLen：1
→ 右边界扩张 right++
L
R
a[0]
b[1]
c[2]
a[3]
b[4]
c[5]
b[6]
b[7]
当前窗口字符集合 Set:
双指针推进总计 ≤ 2N · 耗时 O(N)'a'
窗口初始化：left=0, right=0。字符 "a" 加入集合，当前无重复窗口长度为 1，更新 maxLen=1。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 单向滑动全量扫描 | O(N) | O(N) | O(K) ~ O(1) | 左右指针每个元素至多进出窗口各一次，总体线性。 |
template.java
Map<Character, Integer> window = new HashMap<>();
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
while (window.get(c) > 1) {
char d = s.charAt(left);
window.put(d, window.get(d) - 1);
left++;
}
ans = Math.max(ans, right - left + 1);
}解题核心心法提炼
- 核心前提是「单调性」：扩张窗口只能让某些指标单调递增，收缩窗口只能单调递减。
- 更新全局最优结果的时机取决于问题：求最长通常在合法时更新；求最短通常在满足条件并收缩时更新。
- 用频次数组 (int[128] 或 Map) 记录字符出现次数，以 O(1) 判定窗口是否合法。
常见踩坑警示与避坑指南
- 收缩窗口时忘记在状态池中扣除 left 元素对计数器的贡献。
- 更新结果的位置放错循环内外，导致边界窗口被遗漏。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆