滑动窗口详解

灰太狼 2023-10-11 17:36 8阅读 0赞

最近在刷题的时候看到很多基于滑动的窗口的思想去接解决问题，然后就去简单的研究了一下，下面带着大家一起过一遍，看看滑动窗口到底是什么!!!

## 1.滑动窗口基本思想 ##

滑动窗口究其本质就是一种基于双指针的思想，两个指针指向的元素之间形成一个窗口。

常见的滑动窗口有两类：

*  固定大小类的窗口
 *  大小动态变化的窗口

## 2.应用场景 ##

什么情况可以用滑动窗口来解决实际问题呢？

*  一般给出的数据结构是数组或者字符串
 *  求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
 *  该问题本身可以通过暴力求解

## 3.核心思路 ##

> 在具体使用之前，我们知道窗口实际是两个指针之间形成的区域，那关键就是这两个指针是如何移动的。

*  1.初始时，左右指针left,right都指向第0个元素，窗口为\[left,right)，注意这里是左闭右开，因此初始窗口\[0,0)区间没有元素，符合我们的初始定义
 *  2.开始循环遍历整个数组元素，判断当前right指针是否超过整个数组的长度，是退出循环，否则执行第3步
 *  3.然后right指针开始向右移动一个长度，并更新窗口内的区间数据
 *  4.当窗口区间的数据满足我们的要求时，右指针right就保持不变，左指针left开始移动，直到移动到一个不再满足要求的区间时，left不再移动位置
 *  5.执行第2步

值得我们注意的是：这中间，窗口的更新与维护是很重要的一环，新元素加入窗口，旧元素移出窗口，都需要及时地更新与这个窗口范围相关的数据。

上述说明主要是两个while循环，可以简单抽象成一个模板如下：

int left = 0,right =0;
    while(right指针未越界){
        
      char ch = arr[right++];
      //右指针移动，更新窗口
      ...
      
      //窗口数据满足条件 对于固定窗口而言，就是窗口的大小>=固定值；对于动态窗口，就是从left出发，窗口不断扩充，第一次满足题意的位置
      while(窗口数据满足条件){
        
       //记录或者更新全局数据
       ...
       
       //右指针不动，左指针开始移动一位
       char tmp = arr[left++];
       
       //左指针移动，窗口缩小，更新窗口数据
       ...
      }
      //返回结果
      ...
    }

下面我们通过一个具体的例子来看一下，滑动窗口的具体使用。

## 4.实战 ##

我们以[【438. 找到字符串中所有字母异位词】][438.]为例，来看一下具体使用滑动窗口这一思想。

题目描述：

> 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。  
> 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

![在这里插入图片描述][23b1bbc69eea42d9b8cbaf44eb3e0e9e.png_pic_center]

很明显这种窗口大小固定，窗口内数据满足条件后，开始进行收缩，这个条件是：

> 窗口内的字符串和给出的字符串，字符种类一样，且每一类字符的数量也一致。

从这个描述来看可以使用两个map来记录数据:

*  一个记录窗口内的字符种类和数量，记作window，这个map需要根据窗口的变化来实时更新；
 *  一个记录给定字符串的种类和数量，记作map，这是一个固定的map，不会更新。

如果存在一个窗口，window和map相同，即字符种类和大小完全一样，那么当前的left是一个可行的位置，将其添加到集合。那如何判断window和map是一样的呢？  
![在这里插入图片描述][4050d412995f43b2adb95f2182132f4e.jpeg_pic_center]

事实上，我们就是要在移动指针形成窗口的过程中，判断window和map是否一致。

map是固定的，可以按每一类字符来比较，初始化一个计数器valid=0，如果窗口内某类字符完全一致，那么valid加1，最后如果valid==window.size()那么说明我们找到了一个解。

当然我们引入的valid，就需要根据窗口的更新来更新。

#### 窗口更新（移入数据） ####

更新窗口对应的window：如果该字符在map中，那么需要加入到map计数器中；否则计数器不更新

更新valid：数据移入窗口时，如果当前字符在给定的map中，我们要的字符种类出现了，如果这类字符的数量和给定map中该类字符的数量也一致，那么说明该类字符我们就搞定了。

#### 窗口更新（移出数据） ####

更新valid：数据移出窗口时，如果该字符在map中，说明是我们要处理的字符，其字符数量和map中一致时，此时要移出窗口，valid要减1。

更新window：如果该字符在map中，那map对应的计数器需要减1

具体代码如下：

public List<Integer> findAnagrams(String s, String p) {
        
            List<Integer> res = new ArrayList<>();
    
            Map<Character, Integer> map = new HashMap<>();
            Map<Character, Integer> window = new HashMap<>();
    
            char[] pattern = p.toCharArray();
            char[] arr = s.toCharArray();
    
            for (char a : pattern) {
        
                map.put(a, map.getOrDefault(a, 0) + 1);
            }
            int left = 0, right = 0;
            int valid = 0;
            while (right < s.length()) {
        
                char ch = arr[right];
                right++;
                /**
                 * 新元素加入窗口：什么时候当前元素可以加入窗口并新增valid计数?
                 * 当前元素在 map 中，那么把它加入到window中，加入后，如果在窗口内 该元素的数量和要求该元素数量一致，那么valid++,即该元素满足要求
                 */
                if (map.containsKey(ch)) {
        
                    //加入窗口
                    window.put(ch, window.getOrDefault(ch, 0) + 1);
                    // 不能写== 比较的是两个地址
                    if (window.get(ch).equals(map.get(ch))) {
        
                        valid++;
                    }
                }
                //判断窗口内元素是否满足条件,两个条件：
                // 1）固定窗口，当前窗口数量等于 模式字符串p的长度
                // 2)当前窗口内组成的字符串和模式字符串 是异位词
                while (right - left == p.length()) {
        
                    //固定窗口，判断当前窗口是否是异位词,如果是说明找到了一个位置，把left加入到结果集中
                    if (valid == map.size()) {
        
                        res.add(left);
                    }
                    //right 不动，左指针开始向右，arr[left]元素移出窗口,同时该元素在window中对于的数目也要减去1
                    char tmp = arr[left];
                    left++;
                    if (map.containsKey(tmp)) {
        
                        if (map.get(tmp).equals(window.get(tmp))) {
        
                            valid--;
                        }
                        window.put(tmp, window.get(tmp) - 1);
                    }
                }
            }
            return res;
        }

常见的题目还有：

*  [《76. 最小覆盖子串》][76.]
 *  [《剑指 Offer II 008. 和大于等于 target 的最短子数组》][Offer II 008. _ target]

[438.]: https://leetcode.cn/problems/find-all-anagrams-in-a-string/
[23b1bbc69eea42d9b8cbaf44eb3e0e9e.png_pic_center]: https://img-blog.csdnimg.cn/23b1bbc69eea42d9b8cbaf44eb3e0e9e.png#pic_center
[4050d412995f43b2adb95f2182132f4e.jpeg_pic_center]: https://img-blog.csdnimg.cn/4050d412995f43b2adb95f2182132f4e.jpeg#pic_center
[76.]: https://leetcode.cn/problems/minimum-window-substring
[Offer II 008. _ target]: https://leetcode.cn/problems/2VG8Kg/