哈喽大家好,我是程序员脚趾
算法里有一种东西特别恶心。
你看题解的时候：
哦~ 原来是这样。等自己打开 LeetCode：
left++ 还是 right++ 来着？然后开始：
调半小时
输出一屏 debug
最后发现 valid 少减了一次
没错，我说的就是滑动窗口。
很多人第一次学这个算法，都有一种错觉：
“我会了。”
实际上：
“你只是看会了。”
真正自己写的时候：
while (right < s.length()) {刚敲出来，人已经开始慌了。
这篇文章咱就不搞那种教科书式废话了。
什么：
滑动窗口是一种在线性时间内解决子串问题的算法思想。这种话看了和没看一样。
咱今天直接用人话聊。
你读完至少能做到一件事：
以后再碰到子串问题，不会第一时间原地去世。
顺便还能解决这几个经典题：
| LeetCode | 题目 | 难度 |
|---|---|---|
| 76 | 最小覆盖子串 | Hard |
| 567 | 字符串排列 | Medium |
| 438 | 找所有字母异位词 | Medium |
| 3 | 无重复字符最长子串 | Medium |
一、滑动窗口到底是个啥
先问你个问题。
如果让你找：
一个数组里满足条件的连续子数组你会咋写？
大部分人的第一反应：
for (...) { for (...) { } }暴力枚举。
简单，直接，且超时。
时间复杂度直接干到O(N²)。
LeetCode 看了都摇头。
于是聪明人就发现：
很多区间，其实没必要重复计算。
比如：
[left, right]已经算过了。
下一次你变成：
[left, right + 1]其实只多了一个元素。
那我干嘛重新算一遍？
于是滑动窗口就诞生了。
说白了：
用一个会移动的区间，维护当前答案。
窗口右边负责扩张。
窗口左边负责收缩。
像极了一只毛毛虫。
一会伸长。
一会缩短。
然后边爬边找答案。
二、为什么它是 O(N)
很多人看到这个：
while () { while () { } }立马PTSD发作：
双 while？ 那不还是 O(N²)？其实不是。
因为：
left 和 right 都不会后退。它俩这一生只有一个梦想：
向右走。
每个元素：
最多进窗口一次
最多出窗口一次
所以整体复杂度其实是O(N)。
这就是滑动窗口最牛逼的地方。
三、滑动窗口万能模板
这玩意其实是有固定套路的。
以后你刷题，别硬想。
直接默写模板。
int left = 0, right = 0; while (right < s.length()) { // 1. 右边字符进入窗口 char c = s.charAt(right); right++; // 2. 更新窗口数据 // 3. 判断是否需要收缩 while (窗口不合法) { char d = s.charAt(left); left++; // 4. 更新窗口数据 } // 5. 更新答案 }别看简单。
实际上整个滑动窗口，核心就三件事：
1、什么时候扩大窗口 2、什么时候收缩窗口 3、什么时候更新答案你只要把这三个问题想明白。
代码基本不会错。
真正容易死的地方其实是：
答案到底在哪更新？有的题：
扩张时更新
收缩时更新
收缩结束后更新
第一次写的时候特别容易脑子打结。
四、最经典的一题：最小覆盖子串
题目大概意思：
给你：
s = "ADOBECODEBANC" t = "ABC"让你找：
s 里最短的一个子串要求它必须包含：
A、B、C答案：
BANC这题第一次做的时候，很多人都会陷入一种状态：
我知道是滑动窗口。 但我不知道窗口里该存啥。于是开始瞎写。
然后 valid 当场爆炸。
五、need 和 window 到底是干啥的
这个地方其实特别简单。
你只需要记住：
need：目标欠款 window：当前余额比如：
t = "AABC"那么：
need: A -> 2 B -> 1 C -> 1意思就是：
A 还欠两个 B 欠一个 C 欠一个而 window 就表示：
当前窗口里有多少。
窗口右边扩张：
window.put(c, window.getOrDefault(c, 0) + 1);窗口左边收缩：
window.put(d, window.get(d) - 1);整个算法本质上：
就是在讨债。
欠款补齐了。
窗口合法。
开始缩。
缩到快不合法的时候停下。
六、valid 到底是什么鬼
这玩意第一次看特别抽象。
其实它翻译成人话就一句：
当前有几个字符已经还清贷款了。
比如：
need: A -> 1 B -> 1 C -> 1当前窗口：
A -> 1 B -> 1 C -> 0那说明：
A 和 B 已经达标于是：
valid = 2当：
valid == need.size()说明：
所有贷款全部还完窗口合法。
开始收缩。
七、最容易写错的地方
很多人会问：
为啥更新答案放在 while 里面？因为：
窗口合法的时候，才是候选答案。而我们要的是：
最短。所以窗口一合法：
立马开始压缩。就像搬家收纳。
能扔的全扔。
直到再扔就不合法了。
这时候留下的。
才是当前最优解。
八、完整代码
class Solution { public String minWindow(String s, String t) { Map<Character, Integer> need = new HashMap<>(); Map<Character, Integer> window = new HashMap<>(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); } int left = 0, right = 0; int valid = 0; int start = 0; int len = Integer.MAX_VALUE; while (right < s.length()) { char c = s.charAt(right); right++; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if (window.get(c).equals(need.get(c))) { valid++; } } while (valid == need.size()) { if (right - left < len) { start = left; len = right - left; } char d = s.charAt(left); left++; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len); } }九、真正的滑动窗口思维
很多人学算法。
喜欢背模板。
其实没啥用。
因为一变题就寄。
真正重要的是：
窗口什么时候合法？你只要能判断：
什么时候扩张
什么时候收缩
什么时候更新答案
那这个题就已经做出来一半了。
后面的：
字符串排列
找异位词
最长无重复子串
本质上全是这一套。
只是条件变了而已。
十、最后送你一句话
我后来发现。
滑动窗口其实就一句话：
right 负责把答案搞出来。
left 负责把答案榨干。
窗口不合法：
right 往前冲。窗口合法：
left 开始疯狂压缩。直到榨不动。
这时候留下的。
就是当前最优解。
很多题你一旦用这个视角去看。
会突然发现：
卧槽，原来全长一个样。这才是滑动窗口真正的套路。
