滑动窗口详解_窗口滑动-程序员宅基地

技术标签: java  数据结构  LeetCode  

滑动窗口

基本概念

滑动窗口是一种基于双指针的一种思想,两个指针指向的元素之间形成一个窗口。

分类:窗口有两类,一种是固定大小类的窗口,一类是大小动态变化的窗口。

应用

利用滑动窗口获取平滑的数据,如一段连续时间的数据平均值,能够有更好的稳定性,如温度监测。

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

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

核心思路

窗口的形成

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

  1. 初始时,左右指针left,right都指向第0个元素,窗口为[left,right),注意这里是左闭右开,因此初始窗口[0,0)区间没有元素,符合我们的初始定义
    在这里插入图片描述

  2. 开始循环遍历整个数组元素,判断当前right指针是否超过整个数组的长度,是退出循环,否则执行第3步

  3. 然后right指针开始向右移动一个长度,并更新窗口内的区间数据

在这里插入图片描述

  1. 当窗口区间的数据满足我们的要求时,右指针right就保持不变,左指针left开始移动,直到移动到一个不再满足要求的区间时,left不再移动位置

在这里插入图片描述

  1. 执行第2步

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

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

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

下面就结合所说的方法来看实际的栗子,主要的变化是窗口数据满足的条件,应该根据不同的要求来具体实现。

实战

LC438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
分析

题目的意思从字符串s中选取固定长度的子串,使得子串和给出的p字符串的字符种类相同,且每一种字符的数量也相同,称之为异位词。要求求出所有符合要求的子串的起始位置。

暴力的解法是选取所有子串然后与给定的字符串p进行比较,复杂度较高。

使用滑动窗口的方法来解决,并且是个固定大小的滑动窗口。

窗口内数据满足条件后,开始进行收缩,这个条件是窗口内的字符串和给出的字符串,字符种类一样,且每一类字符的数量也一致。从这个描述来看可以使用两个个map来记录数据,一个记录窗口内的字符种类和数量,记作window,这个map需要根据窗口的变化来实时更新;一个记录给定字符串的种类和数量,记作map,这是一个固定的map,不会更新。

如果存在一个窗口,window和map相同,即字符种类和大小完全一样,那么当前的left是一个可行的位置,将其添加到集合。那如何判断map和window是一样的呢?暴力的方法,就是按每类字符去对比,字符种类一样,每类数量一致,复杂度是O(n),那有没有更好的方法呢?
在这里插入图片描述

事实上,我们就是要在移动指针形成窗口的过程中,判断window和map是否一致。map是固定的,可以按每一类字符来比较,初始化一个计数器valid=0,如果窗口内某类字符完全一致,那么valid加1,最后如果valid==map.size()那么说明我们找到了一个解。

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

窗口更新(移入数据)

更新window:如果该字符在map中,那么需要加入到window计数器中;否则计数器不更新

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

窗口更新(移出数据)

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

更新window:如果该字符在map中,那window计数器对于该计数器需要减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;
    }

LC76. 最小覆盖子串

分析

和LC438很相似,但是本题是一个动态窗口,解题方法同LC438也一致,只是不需要对窗口的大小进行限制。当窗口内的数据满足条件时,就可以进行窗口的收缩了。

代码如下:

    public String minWindow(String s, String t) {
    
        int start = 0, len = s.length() + 1;
        char[] pattern = t.toCharArray();
        char[] arr = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char a : pattern) {
    
            map.put(a, map.getOrDefault(a, 0) + 1);
        }
        int left = 0, right = 0, valid = 0;
        while (right < s.length()) {
    
            char ch = arr[right++];
            if (map.containsKey(ch)) {
    
                window.put(ch, window.getOrDefault(ch, 0) + 1);
                if (window.get(ch).equals(map.get(ch))) {
    
                    valid++;
                }
            }
            //满足条件的窗口 这里不是固定窗口,对窗口大小不限制,当map和window中的数据一致,满足条件,开始收缩
            while (valid == map.size()) {
    
                // 当前已经满足要求,更新并记录数据,同时收缩窗口
                if (right - left < len) {
    
                    start = left;
                    len = right - left;
                }
                char tmp = arr[left++];
                if (map.containsKey(tmp)) {
    
             // 当前要移出的字符种类和数量和map一致,移出后不一致,valid--
                    if (window.get(tmp).equals(map.get(tmp))) {
    
                        valid--;
                    }
                    window.put(tmp, window.get(tmp) - 1);
                }
            }
        }
        return len == s.length()+1 ? "" : s.substring(start, start + len);
    }

事实上,当valid==map.size()时,在窗口window内可能出现比map中对应字符数量多的情况,但是valid并没有变大,是因为在更新valid的时候,只有与map中字符数目相同才更新,如果已经满足了该条件,那么只更新window,不更新valid。

举个例子,s=“BBNAC”,t=“ABC”

第一个满足条件的窗口,B字符出现了2次,但map中只出现了1次。

在移出的时候,只有当当前窗口中该移出字符的数量刚好等于map中该字符的数量时,valid才会-1,表示当前窗口已经不满足要求了,第二个while循环也就不会再继续了,又开始进行right指针的移动了。
在这里插入图片描述

最后

本文对滑动窗口类的一些问题进行了分析,总结了一个模板,并结合Leetcode上的一些例子进行了应用实战。Leetcode相关类型的例子还有LC3、LC513、LC1052等,可以参考利用上述方法进行练习。

迟来的本周更新总算赶上了,希望后续能够保持,与君共勉!

更多信息可关注微信公众号:惊鸿只为卿
在这里插入图片描述

欢迎点赞、关注、分享、在看!

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yjpeng125/article/details/120833365

智能推荐

pytorch与matlab,Pytorch安装 与入门链接-程序员宅基地

文章浏览阅读568次。Pytorch安装 与入门链接发布时间:2018-03-13 15:07,浏览次数:586, 标签:PytorchPytorch安装1)先是Anaconda安装配置,参照原来一篇博客2)Git Clone源代码进入虚拟环境后,采用conda安装:conda install pytorch torchvision -c soumith如果不成功则:那么最后还有一个选择,install from so..._matlab安装pytorch

SpingMVC IReport多数据源交叉报表示例_jaspersoft ireport designer 多数据源-程序员宅基地

文章浏览阅读8.8k次,点赞5次,收藏8次。开始本示例之前,有必要先阅读我先前发布的《SpringMVC与iReport(JasperReports) 5.6整合开发实例》这篇博文,只有熟悉了SpringMVC与iReport的整合基础之后,才能更容易上手本示例教程,因为本示例的重点在于iReport报表_jaspersoft ireport designer 多数据源

angr_angr re-程序员宅基地

文章浏览阅读1k次。angr_angr re

mysql中limit和offset的用法详细介绍_mysql limit offset-程序员宅基地

文章浏览阅读2.2w次,点赞29次,收藏129次。有的时候我们在学习或者工作中会使用到SQL语句,那么介绍一下limit和offset的使用方法。mysql里分页一般用limit来实现,例如:1、select* from user limit 3表示直接取前三条数据2、select * from user limit 1,3;表示取1后面的第2,3,4三条条数据3、select * from user limit 3 offset 1;表示取1后面第2,3,4三条条数据解释:1、当 limit后面跟一个参数的时候,该参数表示要取的数据的数_mysql limit offset

OpenCV3学习(10.1)背景分离 (帧间差分法、背景差分法)_opencv 背景差分-程序员宅基地

文章浏览阅读1.4w次,点赞7次,收藏105次。 背景提取是在视频图像序列中提取出背景,背景就是场景中静止不动的景物。因为摄像机不动,因此图像中的每个像素点都有一个对应的背景值,在一段时间内,这个背景值是比较固定的。背景提取的目标就是根据视频图像序列,找出图像中每一点的背景值。 背景提取有很多算法。针对静止摄像机的帧间差分法、高斯背景差分法,还有针对运动摄像机的光流法等。 一. 帧间差分法相邻帧间图像差分思想:检测出了相邻两帧..._opencv 背景差分

磁共振计算机都是量子技术吗,IBM利用磁共振对单个原子成像,未来用于量子计算机...-程序员宅基地

文章浏览阅读105次。导读:虽然并非是最漂亮的科学设备,这台显微镜能够利用磁共振技术对单个原子成像凤凰网科技讯北京时间 7 月 2 日消息,随着我们的设备尺寸越来越小,越来越复杂,用来制造它们的材料也越来越复杂。这意味着我们必须仔细地开发设计新材料。不同的显微技 ......虽然并非是最漂亮的科学设备,这台显微镜能够利用磁共振技术对单个原子成像凤凰网科技讯北京时间 7 月 2 日消息,随着我们的设备尺寸越来越小,越来越..._核磁共振中运用了量子科技吗

随便推点

solr总结详解教程_key=solr.jvm%3aos.processcpuload&key=solr.node%3ac-程序员宅基地

文章浏览阅读5.6k次,点赞2次,收藏15次。Solr调研总结开发类型全文检索相关开发Solr版本4.2文件内容本文介绍solr的功能使用及相关注意事项;主要包括以下内容:环境搭建及调试;两个核心配置文件介绍;维护索引;查询索引,和在查询中可以应用的高亮显示、拼写检查、搜索建议、分组统计、拼音检索等功能的使用方法。版本作者/修改人日期V1.0gzk2013-06-04 1. Solr 是什么?Solr它是一种开放源码的、基于 Lucene..._key=solr.jvm%3aos.processcpuload&key=solr.node%3acontainer.fs.coreroot.usabl

cocos2d-x ndk adt mac 路径配置_cocos2dx 怎么设置sdk 路径-程序员宅基地

文章浏览阅读1.4k次。export PATH=/bin:/sbin:/usr/local/mysql/binexport PATH=$PATH:/Applications/MacVim-snapshot-68export PATH=$HOME/.rbenv/bin:$PATHexport CLICOLOR=1export LSCOLORS=GxFxCxDxBxegedabagacedexpo_cocos2dx 怎么设置sdk 路径

linux usb声卡 无声音,记一次解决在Ubuntu 18.04下声卡没有声音的经历-程序员宅基地

文章浏览阅读1.6k次,点赞2次,收藏5次。电脑的主板是华硕的B150-PLUS,声卡是瑞昱的intel ALC 887,从Ubuntu 16.04升级到Ubuntu 18.04系统,使用一切正常,但是声卡没有声音。经过查找资料,得出了解决该问题的答案,如果你的Ubuntu 18.04系统也没有声音,可以参考下方的解决方案处理。解决方案1.在Ubuntu 18.04终端中运行以下命令:sudo apt-get remove --purge ..._alc887声卡驱动ubuntu

微信支付-电商收付通开发-02.获取平台证书与图片上传_java实现微信电商收付通get 获取平台证书列表-程序员宅基地

文章浏览阅读3.4k次。文章目录1. 配置类与工具类1.1 okhttp3工具类1.2 微信支付配置类1.3 微信支付工具类2. 获取平台证书与图片上传接口3. 参考链接1. 配置类与工具类引入gradle依赖subprojects { dependencies { ... //微信的apache-httpclient扩展 compile 'com.github.wechatpay-apiv3:wechatpay-apache-httpclient:0.1.5' _java实现微信电商收付通get 获取平台证书列表

queue()方法_queue()-程序员宅基地

文章浏览阅读2.5k次。queue()方法是一个遍历方法,作用是显示或操作在匹配元素上执行的函数队列。刚开始使用这个方法是用它来遍历匹配元素以使用它带有的回调函数来对匹配元素进行操作,在了解到这个方法真正的作用后有点杀鸡用牛刀的感觉。他真正的作用是操作匹配元素上执行的函数队列,其中一点就是在队列末端中放置一个新函数,这点作用正好就被我用来杀鸡了。请注意,当通过 .queue() 添加函数时,我们应当确保最终调用了..._queue()

python3---对windows系统的文件夹与文件属性为隐藏、只读等。os.chdir、os.getcwd、win32api、win32con_python 设置文件 隐藏 只读属性-程序员宅基地

文章浏览阅读4.2k次。python3—对windows系统的文件夹与文件隐藏 参考:python3.4对应下载https://www.jb51.net/softs/416131.html确认是否安装成功,如下:C:\Python34&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;pythonPython 3.4.3 (v3.4.3:9b73f1c3e601, Feb 24 2015, 22:43:06) [MSC v.1600 32 bit (In..._python 设置文件 隐藏 只读属性

推荐文章

热门文章

相关标签