当前位置：首页 > news >正文

为什么滑动窗口总能把人写红温？

news 2026/5/16 12:04:39

哈喽大家好,我是程序员脚趾

算法里有一种东西特别恶心。

你看题解的时候：

哦~ 原来是这样。

等自己打开 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); } }