当前位置:   article > 正文

滑动窗口详解

滑动窗口

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

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++];
   
   //左指针移动,窗口缩小,更新窗口数据
   ...
  }
  //返回结果
  ...
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

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

4.实战

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

题目描述:

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

在这里插入图片描述

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

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

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

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

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

事实上,我们就是要在移动指针形成窗口的过程中,判断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;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

常见的题目还有:

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/604629
推荐阅读
相关标签
  

闽ICP备14008679号