滑动窗口算法总结及相关例题

转x33g5p2x  于2021-11-21 转载在 其他  
字(4.5k)|赞(0)|评价(0)|浏览(379)

这里标注一下，本文参考于 《labuladong的算法小抄》

1. 算法思想

1.1 思想

滑动窗口，顾名思义：滑动的窗口，其实就是使用双指针进行维护一个窗口。经过相关题目的练习，可以得出该窗口大小有固定大小的例题，也有不固定大小的例题。我们要根据相应的题目进行分析。而如果窗口是固定大小的，我们一般会根据窗口大小要超越固定大小而进行缩小窗口。而不是固定大小的窗口的就根据题目具体意思进行相应的窗口缩小。

1.2 套路代码

  1. int l = 0, r = 0;
  2. while(r < s.length()){
  3. 	扩大窗口
  4. 	
  5. 	c是要添加进去的字符
  6.    char c = s.charAt(r);
  7.     r ++;
  8.     
  9. 	这里进行相关的操作
  11.     while(窗口需要缩小时){
  12. 		
  13. 		
  14. 		缩小窗口
  15. 		
  16. 		d是要从窗口中出去的字符
  17.         char d = s.charAt(l);
  18.         l ++;
  20. 		这里进行相关的操作
  21.     }
  22. }

相关模板讲解：

  1. 在这里我们使用的是双指针算法技巧，初始化 l = 0 ,r = 0
  2. 我们这里维护的区间窗口为[l,r)。
  3. r 作为右指针进行扩大窗口，c 是放入窗口内部的字符
  4. l 作为左指针进行缩小窗口，d 是从窗口中去除的字符
  5. 那么其他需要加进来的代码就是题目要求我们维护的相应的数据结构，和维护该数据结构的相关操作了。看我博客的友友们要随机应变哦。

1.3例题精讲

1.3.1 最小覆盖子串

思路分析：

  1. 在扩大窗口的同时，我们需要维护什么？
    因为题目要我们求的是包含相应模板串中的所有字符，那么相应的字符可能是分散于我们求出来的答案中的，所以我们需要去维护一个名为need的map集合存下模板串的所有字符及个数。还要一个名为win的map集合存下相应主串中滑动窗口中是上一个map集合中所包含的字符，还需要一个变量valid存下滑动窗口中和模板串中对应字符的个数相同的字符个数，因为是要求子串，所以还需要一个start记录相应的起始下标，len记录相应的长度。

  2. 什么时候缩小窗口？
    当valid等于need的大小时，就是相应的主串的滑动窗口包含模板串的所有字符了，此时需要缩小窗口。

3.在什么地方、什么时候更新start和len?

在内层while中进行更新。当len 小于 r - l时。

AC代码：

  1. public String minWindow(String s, String t) {
  2.         Map<Character,Integer> map = new HashMap<>();
  3.         Map<Character,Integer> map2 = new HashMap<>();
  5.         for(int i = 0; i < t.length(); i ++) map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0) + 1);
  7.         int l = 0, r = 0;
  8.         int valid = 0;
  9.         int start = 0, len = Integer.MAX_VALUE;
  11.         while(r < s.length()){
  12.             char c = s.charAt(r);
  13.             r ++;
  15.             if(map.containsKey(c)){
  16.                 map2.put(c,map2.getOrDefault(c,0) + 1);
  17.                 if(map.get(c).equals(map2.get(c))){
  18.                     valid ++;
  19.                 }
  20.             }
  22.             while(valid == map.size()){
  23.                 if(r - l < len){
  24.                     start = l;
  25.                     len = r - l;
  26.                 }
  28.                 char d = s.charAt(l);
  29.                 l ++;
  30.                 if(map.containsKey(d)){
  31.                     if(map.get(d).equals(map2.get(d))){
  32.                         valid --;
  33.                     }
  34.                     map2.put(d,map2.get(d) - 1);
  35.                 }
  37.             }
  38.         }
  39.         return len == Integer.MAX_VALUE ? "" : s.substring(start,start + len);
  40.         
  41.     }

特别提醒：

Byte,Short,Integer,Long 这 4 种包装类默认创建了数值 [-128，127] 的相应类型的缓存数据，Character 创建了数值在 [0,127] 范围的缓存数据，Boolean 直接返回 True Or False。 两种浮点数类型的包装类 Float,Double 并没有实现常量池技术。

所以如果是超出相应的范围，就不能使用 ==判断数值大小，而必须使用equals方法

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

思路分析：

  1. 题目分析
    这是窗口大小固定的相关例题。上面那一道是窗口大小不是固定的。

  2. 所需要维护的数据结构？
    因为模板串的字符顺序和主串的不一定相同，所以维护的数据结构和上面的一样。这里不再过多讲解。

  3. 什么时候缩小窗口？
    因为是固定大小的窗口，所以一般是窗口大小等于相应的窗口大小时。先进行 是否符合要求判断，然后进行缩小窗口。

AC代码：

  1. class Solution {
  2.     List<Integer> list = new ArrayList<>();
  3.     public List<Integer> findAnagrams(String s, String p) {
  4.         Map<Character,Integer> need = new HashMap<>();
  5.         Map<Character,Integer> win = new HashMap<>();
  7.         // 初始化need
  8.         for(int i = 0; i < p.length(); i ++) need.put(p.charAt(i),need.getOrDefault(p.charAt(i),0) + 1);
  10.         int l = 0, r = 0;
  11.         int valid = 0;
  12.         while(r < s.length()){
  13.             char c = s.charAt(r);
  14.             r ++;
  16.             
  17.             if(need.containsKey(c)){
  18.                 win.put(c,win.getOrDefault(c,0) + 1);
  19.                 if(need.get(c).equals(win.get(c))){
  20.                     valid ++;
  21.                 }
  22.             }
  24.             while(r - l >= p.length()){
  25.                 // 相应的操作
  26.                 if(valid == need.size()) list.add(l);
  28.                 char d = s.charAt(l);
  29.                 l ++;
  31.                 if(need.containsKey(d)){
  32.                     if(need.get(d).equals(win.get(d))){
  33.                         valid --;
  34.                     }
  35.                     win.put(d,win.get(d) - 1);
  36.                 }
  37.             }
  38.         }
  39.         return list;
  40.     }
  41. }

可以练手的相关题目：

567. 字符串的排列

这里对前面的滑动窗口问题进行总结：

前面的三个问题是难度比较高的三个滑动窗口问题，因为他们的对应的模板串的字符在主串中相应位置不是固定的，所以我们使用valid进行描述到达相应的标准，但是我们需要对我们所确定的区间进行字符记录，且记录的字符要是相应的模板串中含有的。

2. 相关例题

后面的问题就相对比较简单：

2.1. 重复的DNA序列

思路分析：

  1. 题目分析
    其实定长是10，而又是相应的字符串，并且不和前面相应的例题一样，他这相应的字符顺序截取的是什么就是什么，不需要改变。那么就可以直接根据相应的substirng。但是就是需要统计出现的次数。

  2. 维护的数据结构
    map集合。截取后存入相应的map集合，边放边存。然后根据条件进行判断。

AC代码：

  1. class Solution {
  2.     public List<String> findRepeatedDnaSequences(String s) {
  3.         int L = 10;
  4.         List<String> list = new ArrayList<>();
  6.         Map<String,Integer> map = new HashMap<>();
  7.         for(int i = 0; i <= s.length() - L; i ++){
  8.             String a = s.substring(i,i + L);
  9.             map.put(a,map.getOrDefault(a,0) + 1);
  10.             if(map.get(a) == 2){
  11.                 // 为什么是== 2的时候，如果是大于2的话就会导致冗余情况
  12.                 list.add(a);
  13.             }
  14.         }
  15.         return list;
  16.     }
  17. }

2.2. 存在重复元素 II

思路分析:

  1. 题目分析
    这是窗口大小固定的相关例题。上面那一道是窗口大小不是固定的。

  2. 维护的数据结构？
    set 集合，因为需要判断在前面的区间中是否出现过，所以使用set集合

  3. 缩小窗口的时机
    因为这里维护的是[i - k + 1,i]区间，所以当set.size() > k的时候缩小窗口。

AC代码：

  1. class Solution {
  2.     public boolean containsNearbyDuplicate(int[] nums, int k) {
  3.         Set<Integer> set = new HashSet<>();
  4.         for(int i = 0; i < nums.length; i ++){
  5.             // 相当于一个数字在前面的一段区间内只能出现一次
  6.             // 每次遍历的时候加入set集合
  7.             // 该步骤简化了判断在区间距离小于k + 1的情况下是否存在相同元素
  8.             if(set.contains(nums[i])) return true;
  10.             // 在这里进行添加的原因是前面已经判断过了，set集合中不存在相应的重复元素
  11.             set.add(nums[i]);
  13.             if(set.size() > k){
  14.                 // 但是set集合中的元素个数不能超过k + 1个
  15.                 set.remove(nums[i - k]);
  16.             }
  17.         }
  18.         return false;
  19.     }
  20. }

220. 存在重复元素 III

思路分析：

  1. 题目分析
    这里的思路和前面的相似。

  2. 注意点
    但是就是我们这里需要说明的是添加操作的相应的位置改变。因为前面的那一道题是判断过集合不存在相应的元素，才进行添加。而我们这里没有。

  1. if(ts.size() + 1 > k){
  2.   ts.remove(nums[i - k] * 1L);
  3. }
  4. ts.add(nums[i] * 1L);

AC代码：

  1. class Solution {
  2.     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  3.         if(k == 0) return false;
  4.         TreeSet<Long> ts = new TreeSet<>();
  6.         for(int i = 0; i < nums.length; i ++){
  7.             Long u = nums[i] * 1L;
  8.             // TreeSet 是一个可以提供找到大于相应值的最小值 和 一个可以找到小于相应值的最大值的方法
  10.             Long f = ts.floor(u);
  11.             Long r = ts.ceiling(u);
  13.             if(f != null && u - f <= t) return true;
  14.             if(r != null && r - u <= t) return true;
  16.             if(ts.size() + 1 > k){
  17.                 ts.remove(nums[i - k] * 1L);
  18.             }
  19.             ts.add(nums[i] * 1L);
  20.         }
  21.         return false;
  22.     }
  23. }

学到的新知识：

TreeSet : 一个可以提供大于相应元素的最小值和一个可以提供小于相应元素最大值的集合。

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_56727438/article/details/121031724

内容来源于网络，如有侵权，请联系作者删除！

算法算法与数据结构

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com