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

哈喽大家好,我是程序员脚趾算法里有一种东西特别恶心。你看题解的时候哦~ 原来是这样。等自己打开 LeetCodeleft 还是 right 来着然后开始调半小时输出一屏 debug最后发现 valid 少减了一次没错我说的就是滑动窗口。很多人第一次学这个算法都有一种错觉“我会了。”实际上“你只是看会了。”真正自己写的时候while (right s.length()) {刚敲出来人已经开始慌了。这篇文章咱就不搞那种教科书式废话了。什么滑动窗口是一种在线性时间内解决子串问题的算法思想。这种话看了和没看一样。咱今天直接用人话聊。你读完至少能做到一件事以后再碰到子串问题不会第一时间原地去世。顺便还能解决这几个经典题LeetCode题目难度76最小覆盖子串Hard567字符串排列Medium438找所有字母异位词Medium3无重复字符最长子串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) { MapCharacter, Integer need new HashMap(); MapCharacter, 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 开始疯狂压缩。直到榨不动。这时候留下的。就是当前最优解。很多题你一旦用这个视角去看。会突然发现卧槽原来全长一个样。这才是滑动窗口真正的套路。