【滑动窗口】滑窗模板，在小小的算法题里滑呀滑呀滑

女爷i 2024-03-22 18:27 44阅读 0赞

## 首先大家先喊出我们的口号：跟着模板搞，滑窗没烦恼！ ##

![1f1679551e7a4fc390b74e6044a595f4.jpeg][]

## 一.什么是滑动窗口？ ##

> 滑动窗口算法是双指针算法的一种特定化的算法模型，常用于在**特定的条件下求最大或者最小的字符串，特定的数组，以及字符序列等相关问题**，使用滑动窗口的目的也很简单：使原本需要使用双循环嵌套来解决的问题通过双指针来解决，从而使时间复杂度大大降低（一般而言是将O（n^2）的时间复杂度降至O（n））

![5ff3b56b8ecd468ea79eef1c36626935.png][]

## 二.滑动窗口的框架和模板 ##

### 做滑动窗口题目的痛点 ###

> **很多小伙伴在刷LeetCode题目时可能会有这样的感觉：好像这个题是使用滑动窗口来进行解决，怎么解决呢？接着列出了left和right两个指针，之后就不知所措了，这主要对整个滑动窗口算法的执行流程很陌生而导致的，除此之外，即使我们看了题解，知道了解决这个题的整体思路，当我们过两天再来看这个题目的时候，由于缺失了对滑动窗口算法的某些特定步骤的启发，我们还是对这个题目不知所措，经过大佬们们不断的刷题和对滑动窗口算法的总结，滑动窗口的算法模型应运而生~**

### 使用滑动窗口框架的优势 ###

> **滑动窗口框架的优势我们可以从以下几点进行说明：1.使用滑动窗口的框架，能降低整道题目的难度，在特定的难点能够给我们带来启发2.使用滑动窗口的框架，能够使我们将更多的精力放到核心思想的思考上，提高我们刷题的效率。3.使用模板进行开发，当我们回头再来看这个题目时，记忆也会直接锁定到题目中的难点，记忆会更加深刻。**

### **滑动窗口的框架模板如下** ###

### 最长模板 ###

模板的实现思路如下：我们在使用滑动窗口的模板时，对求最长和最短的字符序列或者字符串给出两种不同的实现思路以及模板代码：  
求最长相关的实现思路：

> **左右指针（LR）在起始位置，R指针逐步向右循环滑动，在每次滑动的过程中，如果滑动窗口内的元素满足滑动窗口的需求，R指针不断向右滑动扩大窗口，并不断更新最优结果；如果窗内元素不满足条件，L指针不断向右缩小窗口，在此过程中并不断更新结果，直到R到达结尾**

初始化 left，right，result，bestResult
    while("右指针没有到结尾"){
        窗口扩大，加入right对应元素，更新当前result
        while("result不满足要求"){
            窗口缩小，移除left对应元素，left右移
        }
        更新最优结果bestResult
        right++;
    }
    返回bestResult

### 最短模板 ###

**实现思路：**

> **左右指针（LR）初始在起始点，R逐步向右滑动，在每次滑动的过程中，如果窗口内的元素满足条件，L向右缩小窗口，并不断更新最小的结果，如果窗口内的元素不满足条件，R不断向右扩大窗口，直到R到达字符串的结尾**

初始化 left，right，result，bestResult
    while("右指针没有到结尾"){
        窗口扩大，加入right对应元素，更新当前result
        while("result满足要求"){
            更新最优结果bestResult
            窗口缩小，移除left对应元素，left右移
        }
        right++;
    }
    返回bestResult

## 三.实战分析 ##

### 3.1 [和大于等于 target 的最短子数组][target] ###

#### 题目描述 ####

#### ![58e844ab9b264cd8be67044f335c8f0c.png][] ####

#### 解题思路 ####

> **按照我们上面给出模板的逻辑，我们给出以下的解题思路：定义两个指针（LR），由于这个题目求的是最短的子数组，套用上面的模板，当不满足条件的时候R不断向右移动，当满足条件之后L指针向右移动不断缩小窗口中元素的数量，最终求得所求数组数量的最小值**

#### 示例代码 ####

我们给出实例代码：

class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            //设置最小个数
            int count=0;
            int left=0;
            int right=0;
            int sum=0;
            int minLength=Integer.MAX_VALUE;
            //进行遍历
            while(right<nums.length){
                sum+=nums[right];
                count++;
                while(sum>=target){
                    if(count<minLength){
                        minLength=count;
                    }
                    sum-=nums[left];
                     left++;
                    count--;
                }
                right++;
            }
            if(minLength==Integer.MAX_VALUE){
                return 0;
            }
            return minLength;
        }
    }

###  ###

### 3.2 [最小覆盖子串][Link 1] ###

#### 题目描述 ####

![48f44bbdcb114ad8b1548de3fe7bd3a8.png][]

#### 解题思路 ####

> 大家不要被这道试题的难度吓到，我们要始终相信：**跟着模板搞，滑窗没烦恼！ok，接下来讲述我们这道题的解题思路：这道题是求覆盖目标子串所需要的子串数量，我们首先使用一个hashmap对目标子串所需要的字符以及每个字符所需要的数量进行遍历，定义LR两个指针，由于这个题目仍然是求最小子串，当我们遍历的字符串不满足要求时R指针不断向右遍历，并对窗口内的元素使用另一个hashmap进行存储，当我们遍历过的指针能够满足目标串所需相关字符的数量，这时我们再使L指针不断向右缩减窗口内元素的数量，不断循环这个过程，直到R走到字符串的最后一个元素**

#### 示例代码 ####

我们给出示例代码：

class Solution {
        public String minWindow(String s, String t) {
            //创建双指针
            int left=0;
            int right=0;
            //定义两个hashmap
            HashMap<Character,Integer>map1=new HashMap<>();
            HashMap<Character,Integer>map2=new HashMap<>();
            int start=0;
            int len=Integer.MAX_VALUE;
            //设置要求
            int need=0;
            //设置满足情况
            int satisfy=0;
            //遍历要求
            for(char c: t.toCharArray()){
                map1.put(c,map1.getOrDefault(c,0)+1);
                if(map1.get(c)==1){
                    need++;
                }
            }
            //进行遍历
            int n=s.length();
            while(right<n){
                map2.put(s.charAt(right),map2.getOrDefault(s.charAt(right),0)+1);
                if(map2.get(s.charAt(right)).equals(map1.get(s.charAt(right)))){
                    satisfy++;
                }
                //优化结果
                while(satisfy==need){
                    if(len>right-left+1){
                        len=right-left+1;
                        start=left;
                    }
                    char rm=s.charAt(left);
                    if(map1.containsKey(rm)){
                        if(map1.get(rm).equals(map2.get(rm)))
                        satisfy--;
                    }
                    map2.put(rm,map2.get(rm)-1);
                    left++;
                }
                right++;
            }
            if(len==Integer.MAX_VALUE){
                return "";
            }
            return s.substring(start,start+len);
        }
    }

### 3.3 [字符串的排列][Link 2] ###

#### 题目描述 ####

![fbf9cd421cb444dd8cb5dd0b48516dfa.png][]

#### 解题思路 ####

> **这道题与上面的那道题目类似，同样是需要两个hashmap，一个是用来存储标准的字符以及其每个字符对应的元素的个数，按照上题的思路同理进行遍历，最后有一点不同的是我们最后将得到的最小值进行与符合要求的长度进行比对，相等返回TRUE ，不相等返回FALSE**

### **示例代码** ###

class Solution {
        public boolean checkInclusion(String s1, String s2) {
            //创建双指针
            int left=0;
            int right=0;
            //创建hashmap
            int[]nums1=new int[26];
            int[]nums2=new int[26];
            int maxLength=Integer.MAX_VALUE;
            int ask=0;
            int satisfy=0;
            //遍历要求
            for(int i=0;i<s1.length();++i){
                nums1[s1.charAt(i)-'a']++;
                if(nums1[s1.charAt(i)-'a']==1){
                    ask++;
                }
            }
            //进行遍历
            while(right<s2.length()){
                nums2[s2.charAt(right)-'a']++;
                if(nums2[s2.charAt(right)-'a']==nums1[s2.charAt(right)-'a']){
                    satisfy++;
                }
                while(satisfy==ask){
                    if(right-left+1<maxLength){
                        maxLength=right-left+1;
                    }
                    if(nums2[s2.charAt(left)-'a']==(nums1[s2.charAt(left)-'a'])){
                        satisfy--;
                    }
                    nums2[s2.charAt(left)-'a']--;
                    left++;
                }
                right++;
            }
            return maxLength==s1.length()?true:false;
        }
    }

### 3.4 [找到字符串中所有字母异位词][Link 3] ###

#### 题目描述 ####

![8da58959151744e1ae063ee2b9c94892.png][]

#### 解题思路 ####

> **同样是与上题类似的解法，唯一的区别是在上题的解题基础上我们对每次遍历的minLength进行统计，如果符合我们条件的需求我们就直接将这个集合加入list即可**

#### 示例代码 ####

class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            //创建list
            List<Integer>list=new ArrayList<>();
            //基本类似的解题思路：
            //创建双指针
            int left=0;
            int right=0;
            //创建两个哈希表
             int[]nums1=new int[26];
            int[]nums2=new int[26];
            int ask=0;
            int satisfy=0;
            //遍历要求
            for(int i=0;i<p.length();++i){
                nums1[p.charAt(i)-'a']++;
                if(nums1[p.charAt(i)-'a']==1){
                    ask++;
                }
            }
            //遍历实际的字符串
            while(right<s.length()){
                nums2[s.charAt(right)-'a']++;
                if(nums1[s.charAt(right)-'a']==nums2[s.charAt(right)-'a']){
                    satisfy++;
                }
                //优化结果
                while(satisfy==ask){
                    if(right-left+1==p.length()){
                        list.add(left);
                    }
                    if(nums2[s.charAt(left)-'a']==(nums1[s.charAt(left)-'a'])){
                        satisfy--;
                    }
                    nums2[s.charAt(left)-'a']--;
                    left++;
                }
                right++;
            }
            return list;
        }
    }

### 3.5 [无重复字符的最长子串][Link 4] ###

#### 题目描述 ####

![2f573d5100b346678863e5571a0dbb7b.png][]

#### 解题思路 ####

> **这个题与前面的题目就有相对较大的区别了，从滑动窗口的种类来看，这个求的是最大的滑动窗口的大小，我们具体描述一下这道题的解题流程：创建hash表来存储我们每次进行遍历的元素，创建双指针进行遍历，R指针不断进行向右遍历每遍历一个元素我们就将元素加入到hash表中，当窗口中的元素数量不满足题目要求时（某个元素出现了两次），这时我们就将L指针不断向右移，直到满足题目中的要求，最后将我们最大的maxLength进行返回即可。**

#### 示例代码 ####

class Solution {
        public int lengthOfLongestSubstring(String s) {
            
            //创建哈希表
            HashMap<Character,Integer>map=new HashMap<>();
            //定义双指针
            int left=0;
            int right=0;
            //定义总长度
            int n=s.length();
            int maxLength=0;
            while(right<n){
                map.put(s.charAt(right),map.getOrDefault(s.charAt(right),0)+1);
                while(map.get(s.charAt(right))>1){
                     map.put(s.charAt(left),map.get(s.charAt(left))-1);
                     left++;
                }
                if(right-left+1>maxLength){
                    maxLength=right-left+1;
                }
                right++;
            }
           return maxLength; 
        }
    }

### 3.6 [考试的最大困扰度][Link 5] ###

#### 题目描述 ####

![ba405d237520489fb775ec59bd4d7a5c.png][]

#### 解题思路 ####

> **这个题也是求最小的窗口，我们的解题思路也相对明确：就是用给定的k个万能值来填补两部分TRUE或者FALSE之间的空缺，R指针不断向右移，如果k无法满足空缺的话，L向右移动，直到K能够满足，一直遍历直到R指针遍历到字符串的最后**

#### 示例代码 ####

class Solution {
        public int maxConsecutiveAnswers(String answerKey, int k) {
            //核心思路：使用提供的k的个万能值，来填补TRUE和FALSE之间的空缺值
            //创建两个指针
            int left=0;
            int right=0;
            //创建计数器
            int countT=0;
            int countF=0;
            int n=answerKey.length();
            int maxLength=0;
            //进行遍历循环
            while(right<n){
                char c=answerKey.charAt(right);
                
                if(c=='T'){
                    countT++;
                }else{
                    countF++;
                }
                //不符合的情况
                while(countT>k&&countF>k){
                    char d=answerKey.charAt(left);
                    //进行遍历
                    if(d=='T'){
                        countT--;
                    }else{
                        countF--;
                    }
                    left++;
                }
                if(right-left+1>maxLength){
                    maxLength=right-left+1;
                }
                right++;
            }
            return maxLength;
    
        }
    }

[1f1679551e7a4fc390b74e6044a595f4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/75118e0db7c44942969cd09f632d112e.png
[5ff3b56b8ecd468ea79eef1c36626935.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/069182d2bcf649c0a4b90ea12467df08.png
[target]: https://leetcode.cn/problems/2VG8Kg/
[58e844ab9b264cd8be67044f335c8f0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5779fab72eb74deda75e1cb6dfbb1633.png
[Link 1]: https://leetcode.cn/problems/minimum-window-substring/
[48f44bbdcb114ad8b1548de3fe7bd3a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5f9900e99448455dbd2fb309cd9ce787.png
[Link 2]: https://leetcode.cn/problems/permutation-in-string/
[fbf9cd421cb444dd8cb5dd0b48516dfa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/09e55d6b23ec4f7fafa06cbbf1f2c680.png
[Link 3]: https://leetcode.cn/problems/find-all-anagrams-in-a-string/
[8da58959151744e1ae063ee2b9c94892.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5241cac615c647f1ae2d2d8d82e43eee.png
[Link 4]: https://leetcode.cn/problems/longest-substring-without-repeating-characters/
[2f573d5100b346678863e5571a0dbb7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/a720b511d9f349229439aa785848aacc.png
[Link 5]: https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/
[ba405d237520489fb775ec59bd4d7a5c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/851a58e6bb17452fa37ae907a92bea56.png