滑动窗口-个人理解&学习整理_阅读理解滑动窗口

1. 滑动窗口应用场景&思路

• 找【连续】子串/子数组
• 对子串/子数组有特定要求：最小包含、最大包含、出现次数、无重复、累加等等

在字符串中找子串，肯定就需要指针，再加上判断字符长度那就得需要两个指针(left，right)，那么指针如何移动呢？或者说指针以谁为标准来判断是否可以移动？

那么就需要一个空间对两个指针之间的字符进行储存和判断，我们把它叫做window(一般用HashMap<Character,Integer>，有时也会用int)，也就是说[left, right)区间就是我们的窗口

符合了收缩条件，left移动，此为【缩小窗口】
不符合收缩条件，移动right，此为【扩大窗口】

如果一直满足题意，窗口收缩时不满足题意，窗口收缩时不能更新结果值，需要在收缩结束更新。

通过不断的移动，最终当right超出范围（right>=nums.length）时退出

不过要注意边界数据的处理，比如判空或者字符串/数组中一个符合条件的都没有此时就要注意返回结果的初始值，等等

2. 上代码开干

光看上面的太枯燥了，但是放在开头讲也是为了先简单认识一下，后面做两道题再回头去看就会豁然开朗（不过本人较菜，有问题望大佬指出）

（1）先做一道简单入门题
1876. 长度为三且各字符不同的子字符串
问题描述：
如果一个字符串不含有任何重复字符，我们称这个字符串为 【好字符串】。
给你一个字符串 s ，请你返回 s 中长度为 3 的 【好子字符串】 的数量。
注意，如果相同的【好子字符串】出现多次，每一次都应该被记入答案之中。
子字符串 是一个字符串中连续的字符序列。

示例：

输入：s = "xyzzaz"
输出：1
解释：总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。
唯一的长度为 3 的好子字符串是 "xyz" 。
1
2
3
4

输入：s = "aababcabc"
输出：4
解释：总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。
好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。
1
2
3
4

提示：

    1 <= s.length <= 100
    s​​​​​​ 只包含小写英文字母。
1
2

解题思路
【问题再次描述】
如果一个字符串不含有任何重复字符，我们称这个字符串为 “好字符串”。
给你一个字符串 s ，请你返回 s 中长度为 3 的 “好子字符串” 的数量。
注意，如果相同的 “好子字符串” 出现多次，每一次都应该被记入答案之中。
子字符串 是一个字符串中连续的字符序列。

【大白话阅读理解】
也就是说，我需要从一个父字符串中找长度为3的子字符串，然后这个子字符串必须是在父字符串中连续的，如果重复出现也没事，反正我全都要！！！

【工具伙伴】
我想我需要：

• 两个指针（left，right）来帮我从父字符串中依次连续的划分出子字符串
• 一个存储空间（window）来帮我存储left和right之间已有的字符，既然题目要求不重复那我就用Map来帮我的忙，Map<Character,Integer>，其中Chararter用来存字符，Integer用来存这个字符的个数，如果Integer==0，那么我就移从Map中除去此字符
• 长度方面我用right-left=3来控制，如果right-left=3 && window.size()=3那么就说明此子字符串合理，最终结果res++

【流程步骤】
在说流程之前我们先回顾一下left和right的移动条件：

符合了收缩条件，left移动，此为【缩小窗口】
不符合收缩条件，移动right，此为【扩大窗口】
1
2

• 创建好所有的对象
• 循环遍历父字符串
• 每次循环要先将right所在位置的字符加入到map中
• 判断right-left是否等于3
• 不等于3 说明不符合条件，此时则继续循环
• 等于3 说明符合第一个条件，此时进行下一步判断，即window.size()是否为3，
• 不为3 说明有重复，此时从window中去除一个left所在位置的字符，注意如果去除之后个数为0，则直接从window中remove掉，然后left++
• 为3 说明完全符合条件，此时res++，再从window中去除一个left所在位置的字符，注意如果去除之后个数为0，则直接从window中remove掉，然后left++
• 循环直至right==s.length()
• 返回结果res

【细节处理】
满足题意时窗口收缩，所以更新结果（res++）在收缩过程（left++）中。

【代码】

//窗口状态：窗口内字符的数量
//收缩条件：窗口内字符数量等于3，即right-left==3
 public int countGoodSubstrings(String s) {
 		//创建好所有的对象
        Map<Character,Integer> map = new HashMap<>();
        int left = 0;
        int right = 0;
        int res = 0;
        //循环遍历父字符串
        while(right<s.length()){
        	//每次循环要先将right所在位置的字符加入到map中
            char c1 = s.charAt(right);
            map.put(c1,map.getOrDefault(c1,0)+1);
            //right移动【扩大窗口，直至符合条件】
            right++;
            //判断right-left是否等于3
            //等于3
            if (right-left==3){//此题目有固定长度为3，只要left移动就肯定不是3了，所以这里根本不用while
                //再判断map中的是否符合条件
                //为3
                if (map.size()==3){
                    res++;
                }
                char c2 = s.charAt(left);
                int n2 = map.get(c2);
                //如果-1之后为0，则去除此字符
                if (n2==1){
                    map.remove(c2);
                }else{
                    map.put(c2,n2-1);
                }
                //left移动【缩小窗口，直至不符合条件，在此过程中可以不断地更新res】
                left++;
            }
        }
        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

这道题可以不用滑动窗口但是为了学习我们还是用滑动窗口来解决，同时我写的比较啰嗦，一是希望详细一点，二是想着自己忘了细节之后可以看看，欢迎大佬指出问题

（2）再来一道巩固
下面再来一道题目，两道题目结合将滑动窗口的方法进一步理解和巩固

3. 无重复字符的最长子串

问题描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4

输入: s = ""
输出: 0
1
2

提示：

    0 <= s.length <= 5 * 104
    s 由英文字母、数字、符号和空格组成
1
2

解题思路
【问题再次描述】
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
【大白话阅读理解】
无(手动/doge)
【工具伙伴】

• 既然是找不重复最长子串的长度，首先因为不重复，所以我们需要Map来作为window
• 找子串我们就需要两个指针left，right
• 长度我就需要一个int整数作为结果res

呃。。。好像还是老四样

【流程步骤】
大家都是天才，所以直接上代码（其实是懒得写，直接放在代码注释里面）
【细节处理】
窗口收缩时不满足题意
所以更新结果（res = Math.max(res, right - left)）不在收缩过程（left++）中。

//窗口状态：窗口内字符的数量
//收缩条件：窗口内有字符数量大于1
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0;
        int right = 0;
        int res = 0;
        while (right < s.length()) {
            char c1 = s.charAt(right);
            //这个getOrDefault很好用，如果在Map中存在则直接取出，如果不存在就直接新建一个，后面的+1是因为无论怎样都要在数量上+1
            map.put(c1, map.getOrDefault(c1, 0) + 1);
            //扩大窗口
            right++;
            //如果发现map中有任何的重复出现，则需要将窗口缩小注意还要将map中的对应数量减少，这里要将left逐步变大是因为，无法确定究竟是哪一个位置上的字母重复了，而且left停下来的位置肯定是符合条件的
            while (map.get(c1) > 1) {//这里要用while，left要一直++，直到符合条件为止
                char c2 = s.charAt(left);
                map.put(c2, map.getOrDefault(c2, 1) - 1);
                //窗口缩小
                left++;
            }
            //窗口收缩时不满足题意，退出时刚好满足
            res = Math.max(res, right - left);
        }
        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

上面这道题相当于是先找出有重复的一个子串（right++，扩大窗口），然后再在该子串中找第一个无重复的最大连续子串（left++，缩小窗口），而窗口收缩的过程中并不符合无重复的条件，等到退出循环才找到，此时再更新res

---

有关滑动窗口，再给大家推荐两道题目，相信大家做完之后比我理解的更加深刻！

                                   整！
1

【中等】
209. 长度最小的子数组

 public int minSubArrayLen(int target, int[] nums) {
      int window = 0;//储存窗口之间的数值
        int len = nums.length+1;
        int left = 0;
        int right = 0;
        boolean bool = false;
        while(right<nums.length){
            int n1 = nums[right];
            window += n1;
            right++;
            while (window>=target){//这里因为只要符合条件就要一直移动左指针
                bool = true;
                int n2 = nums[left];
                window -= n2;
                left++;
            }
            if (bool){
                len = Math.min(len,right-left+1);//这里+1是因为上面left的退出时所在的位置并不符合条件，left-1的位置才符合
                bool = false;
            }
        }
        return len>=nums.length+1?0:len;
    }**加粗样式**
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

【困难】
76. 最小覆盖子串

   public String minWindow(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        Map<Character,Integer> maphelp = new HashMap<>();
        //初始化maphelp, 使得一开始的maphelp中只包含t中的char
        for (int i=0; i<t.length(); i++){
            char c = t.charAt(i);
            maphelp.put(c,maphelp.getOrDefault(c,0)+1);
        }
        int size = maphelp.size();
        //下面开始滑动
        int left = 0;
        int right = 0;
        int v = 0;//用来控制缩小窗口，当两map中某一个值对应相等才++
        int len = Integer.MAX_VALUE;
        int start = 0;
        while(right<s.length()){
            //先加再移
            char c1 = s.charAt(right);
            if (maphelp.containsKey(c1)){
                //注意后面有一个+1
                map.put(c1,map.getOrDefault(c1,0)+1);
                if (map.get(c1).equals(maphelp.get(c1))){
                    v++;
                }
            }
            right++;
            while (v==size){
                //这里计算的长度是从start开始到right，每次都取最小
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                char c2 = s.charAt(left);
                if (map.containsKey(c2)){
                    //这里就很巧妙，如果一旦发现相同，才会将v-1
                    if (map.get(c2).equals(maphelp.get(c2))){
                        v--;
                    }
                    map.put(c2,map.get(c2)-1);
                }
                left++;
            }
        }
        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }
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