Leetcode专题 滑动窗口（以第76题 Minimum Window Substring 为例，Java）

什么是滑动窗口？

所谓的滑动窗口，就是说一个窗户，不是向前推开的，而是向两边滑动来开启的。其实滑动窗口，就是我们平时说的塑钢推拉窗。

这种滑动窗口，他的位置虽然可以移动，但是宽度是定死的。还有一种滑动窗口，不仅位置可以移动，而且宽度也可以变，或者你可以理解为左边界和右边界都可以任意移动。现实生活中有一种折叠隐藏式纱窗，它的一端是固定的，另外一端可以拉动。如果它的固定端也可以移动的话，就比较像我们在算法里面遇到的两端可滑动窗口了。

塑钢推拉窗和折叠隐藏式纱窗在显示生活中很有用处，那么滑动窗口算法有什么用处呢？大多数情况下，LeetCode里的字符串算法求特定子串和数组求特定连续子数组的题目都可以用滑动窗口得到最优解。而在现实工作中也是，凡是跟数组和字符串有关的问题，很多都可以用滑动窗口来解决。或者应该说，只要是一个序列，涉及到的特定子序列的问题，很多时候都可以用滑动窗口来解决。

比如在NLP自然语言处理的几乎每一个问题都有滑动窗口的机会，分词，词性标注，等等。

声音也可以是一个序列，那么也有机会用到滑动窗口。

视频、图像处理里面的对象检测，也可以用到滑动窗口。下图是著名的对象检测项目，YOLO里面的滑动窗口识别原理。这个可以理解为二维的滑动窗口，首先把图片切片，然后再基于这些格子去构建滑动窗口，本文不具体聊这类的滑动窗口。

OCR里面也需要滑动窗口算法，一般的印刷体文件的OCR使用1维的滑动窗口算法，也就是我们今天聊的这种。

而现在Google翻译以及其他一些软件可以提供的，在任意照片和摄像头流里面找到现实生活中的文字，识别或者翻译，则需要复杂的文本检测算法，这时候需要的滑动窗口，其实是和YOLO类似的二维滑动窗口算法。

​

不管你是处理数组、字符串、音频、视频、图片、文本还是OCR问题，里面涉及到的滑动窗口问题本质上是一样的，甚至框架代码都可以丝毫不改的套用，唯一需要修改的是里面涉及到的业务逻辑。

在只考虑一维滑动窗口问题的时候，其实就两种最大的区别，固定宽度的和可变宽度的滑动窗口。我们举例子分析以及用实际的LeetCode问题的解题来做具体实践。我不敢保证我写的滑动窗口代码最好，甚至比较好，我尽量想把这个过程解释的足够清楚，让完全对这个算法没有基础的朋友，在认真阅读后也能看懂。（但是代码你不写，肯定是不会懂的）

1、固定宽度滑动窗口

首先，我们假设给定一个字符串s，要求你找到这个字符串的k位子串，要求这个子串里面，字符x的出现次数最多。

例如：

s = “abaaaccsddaa”

k = 3

x = ‘a’

这个例子你可能一目了然知道aaa是’a’出现次数最多的子串。

s = “abcdeaaadfewfsaaadassaaaaaddddaass”

k = 5

x = ‘a’

这个就稍微难一点了。这个题目用滑动窗口来做非常自然。我们第一组数据图示如下：

我们观察这个数据和窗口，窗口左边的取值范围是0到字符串长度12-窗口宽度3等于9，右边的取值是2到11。只要一个循环，所有宽度为3的窗口，我们都可以遍历到。

所以，我们可以简单的写一个循环体：

显然，我们应该在do something这里做点事情。那么最简单的思路就是用i也就是左边界和右边界，得到一个s的子串，然后写个子循环，从j从0到k，来统计a的数量，保存一个a的数量的最大值max，跟它比较，如果当前的a的数量大于历史记录，那么就让max等于a当前的数量。

但是这样做，其实就失去了使用滑动窗口的优势。因为复杂度变成了O((N-K)*K)。滑动窗口的好处是，可以让这个处理一次循环得到结果，也就是说，复杂度应该是O(N)。

那么怎么做到呢？其实是，每次循环，首先把滑动带来的新的右边界元素加入，然后去掉原来左边界的元素。比如你用一个数组Nx来保存字符x=’a’的出现次数。那么每次循环你判断right所在字符是不是’a’如果是，Nx++。然后你判断i-1所在字符是不是’a’，如果是Nx–（i-1>=0的前提下）。然后，这时候Nx就是当前的循环次数内，’a’出现的次数了。（循环开始前，你需要先用for循环把前两个字符计算一下）

代码如下：

这里用了两个循环，虽然复杂度没有升高，但是看着有点乱，我们发现如果我们用right做循环变量，代码可以简单一点。因为我们可以让right从0到s.length，而left = right-k，如果left<0就不做字符出窗的处理即可。那么代码如下，稍微简洁了一点：

2、可变宽度滑动窗口

固定宽度的滑动窗口比较好理解。那么当左边右边都可以自由滑动的时候，不用顾忌两者之间距离的时候，那么滑动窗口的思路可以保证遍历到全部的可能行么？当思考连续子串的时候，我们很容易想到双层循环可以保证遍历到每一个可能性。但是那复杂度就是O(N^2)。

当右端指针right=n的时候，左端指针的取值为left从0到n。如果我们for循环用right为变量，然后每次right+1以后，我们都让left从0到n一次，如下图，那么我们实际上的复杂度也是变种的O(N^2)。 所以这是错误的实现方法。

我们以LeetCode的第76题来讲解正确的可变宽度滑动窗口是怎么实现的。

题目 在此（76. Minimum Window Substring） ，要求如下：

给定字符串S和T，找到S的一个最小子串，里面包含了T的所有字符。

例如：

输入为: S = “ADOBECODEBANC”, T = “ABC”

输出为: “BANC”

注意：

• 如果没有这样的子串，返回空字符””即可。
• 如果有这样的子串，数据可以保证只有唯一的这么一个子串。

我们来分析这道题，目标是在S里面找到包含ABC三个字符的最小子串。那么ABC可以BAC也可以，AXBC可以，BCXA也可以。所以判定条件就是一个子串里面是否有ABC的各种组合。那么按照刚才错误的思路，就是构建双层循环，然后每次循环里面检查是否有这么一个子串。那么对的可变宽度滑动窗口怎么做呢？

首先我们从字符串T提取需求，就是有几个字符，每个字符出现几次，我们把这个信息保存在一个哈希表tdict里面。我们做另外一个sdict哈希表，来统计窗口里字符出现的次数。

我们让left和right都等于0。开始移动right，移动的时候，right对应的字符进入我们的窗口。比如我们现在有三个条件要满足，就是要有A，有B和有C。我们用一个计数器count来测量，窗口里面几个条件满足了。right对应的字符进入窗口，我们看它在不在tdict里面，在的话，我们就更新sdict，然后看这个字符在窗口的统计数字是否等于tdict里面的数字，等于就有一个字符满足条件了，count就+1。

如果count=3，就等于满足了全部条件。如果count等于3或者大于3，我们就开始扩大left从而缩小窗口。然后直到又开始不满足条件。那么就开始新的循环放大right。

所以这个模式就是right增大，一直增大到满足条件，然后left增大，直到不满足条件。然后就增大right。一直循环到right到达最大值，和left也到达了不满足条件的最大值，程序就结束了。下面我们用这道题的例子数据来做一个演示一下这个过程。

那么76题的代码如下：

首先是函数开始和变量初始化：

然后是right循环的开始，把在right位置的字符，放进窗口，进行统计。count不够就继续右移right。

​

​

然后仅当count达到要求的时候，才会走进这段，在这段里面，只要count满足要求，我们就右移left来破坏count。首先，目前count满足要求，于是我们如果窗口字符比标准答案短则，则ans=窗口字符。然后，left当前字符出窗口，然后left右移，统计，更新sdict和count。直到count不满足条件则退出循环。

​

代码开始长起来，为了大家方便，我把我成功实现了的算法都放在一个github里面，地址是 https://github.com/tinyfool/leetcode 。注意，只有文章里面宣布的代码才保证是一定对的。里面也有可能有我实验的代码。未来，我可以优化一下结构让大家更一目了然，不过目前为止，上篇文章和本文对应的代码，都在这个代码库里面。

好了，可变宽度滑动窗口算法的基本思路就介绍到这里了。不过还有一个细节要讲。我们继续回顾，这种算法的大致逻辑是right循环，让字符进窗口（或者是数组），然后用某种方式统计是否满足条件，满足条件则比较长短或其他细节条件，然后移动left让条件不满足，不满足后，继续移动right。直到整个字符串或者数组都被一遍遍历完成。

我们的例子里面我们用了两个hashmap来保存原有字符串条件和窗口字符串的数据。那么有没有更高效的方法呢，其实是有的。这类题目最常见是字符串，所以，常见方法是用char数组来保存统计信息。如果是数字数组，而数字的取值范围是已知的，比如最大数字不超过2万，也可以用数字数组来做。因为char的取值范围只有0-255，那么空间复杂度一定很低，但是时间复杂度则比hashmap更低。数字数组呢，则要具体问题具体分析，时间复杂度一定是最低，但是数字取值范围太大的话，容易造成太大的内存消耗，有可能会得不偿失。

我们还是看76题，用这个思路该怎么做。其实循环体以及其他部分都可以丝毫不改，就是把涉及到hashmap的部分换成数组即可。

初始化部分的区别：

先是hashmap版本

然后是字符数组版本（因为要计算需要符合几个字符的条件，所以，还需要把有数据的字符，再统计一下看有几个）：

hashmap版本，字符进入窗口：

字符数组版本，字符进入窗口

hashmap版本，字符出窗口

字符数组版本，字符出窗口

代码稍微有点绕，我们在用图片解释一下（当然用字符数组实现这个算法的做法可能有n种，但是基础思路是一样的，实现可能略有差别）：

首先是我们的基础数据结构，S和T没啥变化。字符数组dict，一开始都是0。这是一个0-255的数组，我们只把S里面出现的字符对应的字符格子画出来，一目了然，其他的格子都是省略号，他们肯定不参与运算不用理会。

然后，我们把T的数据灌进字符数组dict，那么就是ABC分别统计有一次出现。

然后我们看，我们怎么让字符进入窗口，从刚才的代码上来看，入窗口的方法是字符对应的索引的数字减一。我们会发现，如果字符本来就在T里面，入窗口一次就减一个，如果T里面出现了1次，那么入窗口一次，对应的索引就变为0。但是如果字符不在T里面，入窗口就会造成对应的索引编程负数。

所以，我们代码就写成，“入窗口的时候是字符对应的索引的数字减一”，如果该数字减一后等于0，我们就认为当前字符符合了基本条件，count就加一。

我们举例，现在假设A入窗口，那么dict里面A就等于0了。

但是，假设回到初始状态，我们让D进入窗口，我们会发现，D就从0变成了-1。

如果刚才进了窗口的A，出窗口，那么是在A位置上+1，这时候A就大于0了。这就造成A不符合条件，count就减一。而D，从刚才进窗口的状态出窗口+1的话，就变成了0。所以，你就会发现，因为初始状态的不同。导入T的数据后，有数字的字符，在进窗口的次数等于数字，也就是在这个字符上跟T的统计结果相等的时候，会变成0。而在出窗口的时候，一旦这个字符，进-出小于T中统计数字一样的次数，那么他就一定是大于0的。所以，用进的时候是否变成0，出的时候是否大于0，我们就可以轻松地检验count是应该加还是减。

而不在T里面的字符，虽然初始化的时候是0，但是进窗口就会让自己变成负值，因为进出是对应的，那么它怎么进都是负值，而只有出去的时候能恢复成0。不在T里面的字符在进出的时候的特征都与在里面的字符豪不相同，则正好被略过不会被检测出来。

这个思路稍微有点绕，大家可以在纸面上做一些例子，一步一步的进窗口出窗口，看dict的变化，这样应该就能搞明白边界条件变化的原因了。

为什么要这么折腾的去用字符数组呢？因为效率很高。76题，我用hashmap和用字符数组的代码复杂度完全相同，框架循环代码完全相同。但是hashmap的提交结果是，执行时间为34毫秒。而我的字符数组版本执行时间为4毫秒，8.5倍的速度差异，在现实中完全可以考虑代码复杂度稍微高一点采用字符数组版本来提高性能。

这个代码也在github里。我的建议是076会做以后，可以按照我介绍题目的顺序把这些题目都自己做一遍，做完了，可以跟我对一下，或者做不出来可以跟我对一下。理论上076会做了，这些题目其实都大同小异。