滑动窗口算法

今天复习了一下滑动窗口算法的框架，我第一次看的时候是有点懵逼的，现在回过头来再看一次的时候发现框架和思路都非常清晰，瞬间豁然开朗。下面会以四道力扣上的题来进行举例说明滑动窗口算法的奥秘。

  • 76.最小覆盖字串（困难）
  • 567.字符串的排列（中等）
  • 438.找到字符串中所有字母异位词（中等）
  • 3.无重复字符的最长子串（中等）

基本框架

滑动窗口算法其实是有一点双指针的技巧在里面的，技巧思路其实就是维护一个窗口，不断通过滑动这个窗口，然后同时更新答案。

基本框架如下：

1
2
3
4
5
6
7
8
9
10
11
int left = 0, right = 0;  //定义左右两边的指针
while (right < s.size()) {
 // 增⼤窗⼝
 window.add(s[right]);    //将搜索字符添加进入窗口
 right++;                 //窗口右移
 while (窗口需要缩小时) {
 // 缩⼩窗⼝
 window.remove(s[left]);   //移除窗口最左边的字符
 left++;                   //窗口左移
 }
}

完整框架

只要理解了该框架，基本上可以秒杀大部分滑动窗口问题。其核心思路，也就是我们该如何向窗口中添加新元素，什么时候应该缩小窗口，在窗口滑动的哪个阶段应该更新结果。

框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void slidingWindow(String s, Strint t){
Hash map<char,int> need = new HashMap;
Hash map<char,int> window= new HashMap;
for (char c: t) need[c]++;
int left = 0; 
int right= 0;
int valid= 0;
while(right<s.size()){
    char c = s[right];
    right++;
    //执行窗口内数据的一系列更新操作
    ...
    //判断左侧的窗口是否要收缩
    while(窗口需要收缩){
         //d是需要移出窗口的字符
         char d = s[left];
         //向左移动窗口
         left++;
         //执行窗口内数据的一系列更新操作
         ...
    }
 }
}

滑动窗口算法思路

1.我们对于字符串S中使用双指针中的左右指针技巧，初始化左右指针为left=right=0，把索引左闭右开区间[left，right）称为一个窗口Window。

2.首先在满足不超过字符串S长度的情况下，我们不断的将right指针向右移动，left指针先不变，达到扩大窗口的效果。直到窗口中的字符串包含了T字符串中的所有字符串，right指针则停止移动。

3.此时，left指针开始向右移动，达到缩小窗口的效果，直到窗口中的字符串不再包含T中的所有字符串了，那么我们就要停止left指针的移动了。并且每次增加了left指针都要更新一次数据结果，比如说我们要更新窗口内符合要求的字符串有多少。

4.重复第2和第3步的操作，直到right指针到达字符串S的尽头。

下面根据图片来理解一下，其中集合need和window就是相当于两个计数器

不断将right指针向右移动，直到[left,right]中包含了T中的所有字符。

当满足所有要求后，left指针就开始向右移动，不断的缩小窗口达到最优化结果。

当窗口内的字符串都符合要求了，那么这个left指针就停止移动了。

之后就是重复上述的过程了，首先移动right再移动left，直到right指针到达字符串S的末端，程序结束。为什么要重复移动呢？因为你不能保证你第一次拿到的窗口就是最优的，因此要继续往下搜索。如果到达程序的末尾都没有比第一次得到的窗口更优了，那就可以直接返回结果了。

框架如何使用

首先就是要初始化两个哈希表，记录窗口中的字符和需要凑齐的字符。

然后就是使用left和right指针初始化窗口的两端。

1
2
3
4
5
int left = 0, right = 0;
int valid = 0; 
while (right < s.size()) {
 // 开始滑动
}

其中valid是表示窗口中满足need条件的字符个数，如果valid和need.size的大小相同，则说明窗口已经满足条件，即已经包含了T字符串中的所有字符。

套模板之前，我们需要思考一些问题：

1.当移动right指针扩大窗口时，即加入字符到窗口Window里面时应该更新哪些数据呢？

2.在什么条件下，窗口应该停止扩大，开始移动left缩小窗口？

3.当移动left缩小窗口的时候，也就是移除字符时，应该更新哪些数据呢？

下面就用几道例题来说明一下

例题