滑动窗口算法专题

滑动窗口简介

滑动窗口就是利用单调性，配合同向双指针来优化暴力枚举的一种算法。

该算法主要有四个步骤

1. 先进进窗口

2. 判断条件，后续根据条件来判断是出窗口还是进窗口

3. 出窗口

4.更新结果，更新结果这个步骤是不确定的，应题目要求判断是在进窗口前更新结果还是出窗口前更新结果。

1. 长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

题目细节信息：

1.数组中都是正数 2.在数组中找到长度最小的子数组且子数组中的元素和小于target值

解法：滑动窗口

我们先定义一个left指针和right指针，left和right之间就是一个窗口。在定义一个变量sum来记录[left,right]区间的和。

根据题目要求，我们先确定第一个sum大于等于target值得右边界，所以我们先让right不断进窗口。

以题目中的实例1为例

接着我们根据sum的值来判断是否进窗口还是出窗口。sum的值无非会遇到两种情况。

当sum小于等于target的时候，我们先要更新最小长度和sum的值，接着在进窗口，即让left++

如下图：

之前left指向的元素已经不在窗口里面了，这也是理解出窗口的一个图解。

当sum小于target时，我们进窗口进行了，即right++

滑动窗口的正确性

为什么能判断滑动窗口是对的呢？

因为数组中的数据都是正数，当right找到第一个边界使sum大于等于target的值时，我们就没必要让right继续向后走了，因为数组中都是正数，right继续走下去，sum会变大，但是len也会变长，此时len肯定就不是我们要的结果了。所以不让right向后走，就避免了其他不符合题意情况的枚举了。

代码实现

代码一：我写的形式

    public int minSubArrayLen(int target, int[] nums) {
        int n=nums.length;
        int left=0,right=0;
        int ret=Integer.MAX_VALUE;
        int sum=nums[right];
        while(right<n){
            if(sum<target){
                right++;//进窗口
                if(right<n){
                    sum+=nums[right];
                }
            }else{
                ret=Math.min(ret,right-left+1);//更新长度最小值
                sum-=nums[left];//更新sum值
                left++;//出窗口
            }
        }
        return ret==Integer.MAX_VALUE?0:ret;
    }

代码二：

    public int minSubArrayLen(int target, int[] nums) {
        int n=nums.length;
        int len=Integer.MAX_VALUE;
        int sum=0;
        for(int left=0,right=0;right<n;right++){//进窗口
            sum+=nums[right];
            while(sum>=target){//这里要用while循环
                len=Math.min(len,right-left+1);//更新最小长度
                sum-=nums[left];//更新sum的值
                left++;//出窗口
            }
        }
        return len==Integer.MAX_VALUE?0:len;
    }

2.无重复字符的最长字串

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目解析：在字符串中找到一个连续且无重复字符的子字符串，并返回其长度。

解法一：暴力枚举(会超时)

枚举从字符串的第一个字符开始往后，无重复字符的子串可以到什么位置，找出一个最大长度的即可。

因此，我们可以通过一个哈希表来记录往后枚举的过程中，字符是否出现重复的情况。

//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int ret = 0;
        for(int i = 0; i < len; i++) {
            int[] hash = new int[128];
            for(int j = i; j < len; j++) {
                hash[s.charAt(j)]++;
                if(hash[s.charAt(j)] > 1) {
                    break;
                }
                ret = Math.max(ret, j - i + 1);

            }
        }
        return ret;
    }
}

解法二：滑动窗口

此时，我们可以通过滑动窗口来优化上面的暴力枚举。

首先，先通过一种枚举的情况来分析，如下图

当我们枚举时，当right遇到第一个重复的字符a时，我们就不必要让right继续往后走了，因为前面的left的位置没变，当right继续往后走，left和right之间是一定有重复的字符的。

所以，此时，我们可以让right先固定在原地，先让left指针往后走，直到left指针跳过重复的字符，right才能继续完后走。

但是，当left往后走的时候，right没必要往回退到和left一样的位置，因为当left没有跳过第一个重复的字符时，right撑死只能走到第二个a的位置，且left往后走了，此时子串的长度肯定是比left没有往后走时短的。

两个指针没有回退，这时就可以使用滑动窗口了。

这里先解释下上面的hash数组的意思

这里hash数组的下标为字符串中字符的ASCII值，hash数组中的数据是该字符的出现次数。

滑动川口的解题步骤：

1.进窗口：让字符进入hash表中

2.判断和出窗口：判断该字符是否重复出现，如果重复出现，则出窗口，即将该字符从hash表中删除。

3.更新结果：这里是先进行判断后，才执行更新的操作。

代码实现：

时间复杂度：O(n)
空间复杂度：O(n)
    public int lengthOfLongestSubstring(String ss) {
        int n=ss.length();
        char[] s=ss.toCharArray();
        int[] hash=new int[128];
        int left=0,right=0,ret=0;
        while(right<n){
            hash[s[right]]++;//进窗口
            while(hash[s[right]]>1){//判断字符是否重复出现
                hash[s[left++]]--;//出窗口
            }
            ret=Math.max(ret,right-left+1);//更新结果
            right++;
        }
        return ret;        
    }

3. 最大连续1的个数

题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

题目解析：最多可以将数组中的k个0翻转为1，返回数组经过翻转后，数组中连续1的最大个数。

虽然题目中是要求我们翻转0，但是如果我们遇到0就将其翻转为1的话，接着进行新的枚举的时候，就又要将翻转过的0，重新翻转为0，此时，代码就会很难写，且很复杂。

其实，我们可以转换为求区间的长度，只要该区间的0的个数没有大于k个就行了。

解法一：暴力枚举+zero计数器

定义一个left和right指针，我们可以让left为起点向后枚举，定义一个zero变量来保存枚举过程中遇到0的个数，如果zero的值大于k，此时我们就可以让right指针停在该位置了，因为此时right如果继续走下去，left和right区间就是不符合题目要求了。

也就是说，此时以left为起点的枚举，得到的连续1的长度就是一个最优解了，此时就可以更新结果

所以，我们要换一个起点进行枚举，既让left++，接着让right回到left的位置，以新的left为起点继续，right继续向后枚举，重复上面的步骤。

解法二：滑动窗口

再暴力枚举上进一步优化，当我们让left++的时候，没必要将right重新指向left的位置，因为当zero的值大于k时，right撑死也时只能走到刚才停止的位置，只有我们left跳过一个0的时候，让zero减一，让zero的值小于k时，此时right才可以继续完后枚举。

此时，发现，left和right指针是同向运行，且不会退，我们就可以使用滑动窗口算法来解决该问题。

步骤一：进窗口

当right完后枚举时，遇到1就忽略，如果遇到0，就让zero的值加1

步骤二：判断+出窗口

当zero的值大于k时，我们就出窗口，也就时让left++，如果left遇到1就忽略，如果遇到0，就

让zero的值减1

步骤三：更新结果

此时，更新结果的步骤是在判断的步骤之后。

代码实现：

//时间复杂度：O(n)
//空间复杂度：O(1) 
   public int longestOnes(int[] nums, int k) {
        int left=0,right=0,zero=0;
        int n=nums.length;
        int ret=0;
        while(right<n){
            if(nums[right]==1){
                right++;
            }else{
                right++;
                zero++;//出窗口
            }
            while(zero>k){//判断
                if(nums[left]==0){
                    zero--;//进窗口
                }
                left++;
            }
            ret=Math.max(ret,right-left);//更新结果
        }
        return ret;
    }

注意：这里更新结果为什么不是right-left+1呢？因为我是再right++之后再更新长度，而不是再right++之前更新长度。

更简练版本：

    public int longestOnes(int[] nums, int k) {
         int ret = 0;
         for(int left = 0, right = 0, zero = 0; right < nums.length; right++){
                 if(nums[right] == 0) zero++; // 进窗⼝
                 while(zero > k) // 判断
                 if(nums[left++] == 0) zero--; // 出窗⼝
                 ret = Math.max(ret, right - left + 1); // 更新结果
          }
               return ret;
 }

这个版本就是再right++之前更新长度，所以更新长度时是right-left+1

4.将x减到0的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

题目解析：

1.我们每次进行一次删减操作时，我们都要将数组最左边或最右边的元素删去，供下一次删减操作时使用

2.数组里面的都是正数

在该题中，只有数组里面全是正数，我们才能使用滑动窗口解决

分析：因为当数组里面有负数或者为0的数据时，当right到达第一个停止的位置时，当我们的tmp减去一个负数或者数据为0的数时，由于负数或0的缘故，会导致[left，right]区间的和有可能是等于或大于tmp的，所以，此时进行新的枚举时，right有可能会向前退，也有可能继续向后退。

解题思路转换：解决该题的时候，我们有时候会删去最左边的元素，有时候会删去最右边的元素，但是这种情况太复杂了，我们要转换思路。

正难则反：

题目要求我们找到数组两边使x值减为0的最小个数，我们就可以转换为求中间和为sum-x的最长子串。

解法一：暴力枚举

套两层for循环，遍历每一个子数组的情况，根据子数组的和是否等于target的值，我们就更新结果，接着break跳出一层循环。

解法二：滑动窗口

我们通过滑动窗口来优化枚举，我们每进行一次新的遍历的时候，我们发现没必要每次都让right回到left的位置，因为数组里面都是正数，当left++之后，[left，right]区间的和肯定是小于target的。

此时，发现left和right指针都不回退，此时就可以使用滑动窗口。

1.进窗口：tmp+=nums[right]

2.判断+出窗口：判断tmp的值是否大于target，如果大于出窗口，即nums-=nums[left++]

3.更新结果：当tmp的值等于target的时候，我们就可以更新结果。

//时间复杂度：O(n)
//空间复杂度：O(1)
    public int minOperations(int[] nums, int x) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        int ret=-1;
        int target=sum-x;
        //处理细节，
        if(target<0) return -1;
        for(int left=0,right=0,tmp=0;right<nums.length;right++){
            tmp+=nums[right];//进窗口
            while(tmp>target){//判断
                tmp-=nums[left++];//出窗口
            }
            if(tmp==target){
                ret=Math.max(ret,right-left+1);//更新结果
            }
        }
        if(ret==-1) return -1;//此时没有找到子数组和为target的子数组
        else return nums.length-ret;
    }

5.水果成篮（从这里开始比较认真）

题目连接：904. 水果成篮 - 力扣（LeetCode）

题目分析：有一个fruit数组，在数组中，不同元素的值代表不同的水果种类，相同元素的值代表水果的种类相同，我们有两个篮子，每个篮子只能装一种水果，一个篮子中装的水果数量没有限制。如果摘水果的过程中，一旦遇到与篮子中水果种类不同的水果树，就停止采摘，求这两个篮子能装的最大水果数量。

以上可以总结为一句话：找一个连续的最长子数组，该子数组中的水果种类不超出两种。

解法一：暴力枚举+哈希表

我们可以将每一个子数组的情况枚举出来，枚举的过程中，我们可以借助一个hash表来保存枚举过程中采摘水果的种类和数量。

我们用left为外层循环的标志，right为内层循环的标志

枚举的小细节：

1. 为了防止在[1,2,1]的情况下，right指针会造成数组越界，所以我们每次进行一次内循环时，要对right指针进行判断，是否越界。

2.当篮子中水果的种类也超出两种时，也应该跳出该内层循环

3.在每一次采摘水果之前，必须判断水果种类为2种时，下次采摘的水果是否为第三种水果，如果成立，则跳出内部循环

4.每次进行一次新的外部枚举时，我们也要将hash表中上次枚举保存水果的情况删掉。

代码

//空间复杂度:O(n)
//时间复杂度:O(n^2)
    public int totalFruit(int[] f) {
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        int ret = 0;
        for (int left = 0; left < f.length; left++) {
            for (int right = left; right < f.length; right++) {
                if (right == f.length || hash.size() > 2) {//判断数组是否越界和水果种类的数量
                    break;
                }
                int in = f[right];
                if (hash.size() == 2 && !hash.containsKey(in)) {//摘水果之前的判断
                    break;
                }
                hash.put(in, hash.getOrDefault(in, 0) + 1);
                ret = Math.max(ret, right - left + 1);
            }
            hash.clear();//在下次枚举之前，删除此次枚举的情况
        }
        return ret;
    }

解法二：滑动窗口

当我们进行新的left的枚举时，我们没必要让right重新回到left的位置，因为当left进行新的枚举时（left往后走），如果right重新返回到left指针的位置，往后枚举的时候，right会出现两种情况，第一种情况：right会停在在上一次left枚举时，right的最后枚举的位置或者超过right最后枚举的位置。也就是说，以新的left为新的起点，进行right的枚举时，right是一定会经过之前的枚举停下的位置的，所以，我们就不必要将right返回到left的位置。

通过上面的分析，发现left和right指针是同向双指针，这时我们就可以使用滑动窗口来解决这个问题。

解题步骤

1.定义left=0，right=0

2.进窗口：让hash[f[right]]++

3.判断+出窗口（一个循环）：

当hash.size>2时，让hash[f[left]]--，同时让left++

4.更新长度

用哈希表来实现:

//时间复杂度：O(n)
//空间复杂度：O(n)
    public int totalFruit(int[] f) {
        Map<Integer,Integer> hash=new HashMap<Integer,Integer>();
        int ret=0;
        for(int left=0,right=0;right<f.length;right++){
            int in=f[right];
            hash.put(in,hash.getOrDefault(in,0)+1);//进窗口
            while(hash.size()>2){//判断
                int out=f[left];
                hash.put(out,hash.get(out)-1);//出窗口
                if(hash.get(out)==0){
                    hash.remove(out);
                }
                left++;
            }
            ret=Math.max(ret,right-left+1);//更新长度
        }
        return ret;
    }

用数组来实现：

    public int totalFruit(int[] f) {
        int n=f.length;
        int[] hash=new int[n+1];
        int ret=0;
        for(int left=0,right=0,kind=0;right<n;right++){
            int in=f[right];
            if(hash[in]==0){
                kind++;
            }
            hash[in]++;//进窗口
            while(kind>2){//判断
                int out=f[left];
                hash[out]--;//出窗口
                if(hash[out]==0){
                    kind--;
                }
                left++;
            }
            ret=Math.max(ret,right-left+1);//更新长度
        }
        return ret;
    }

6.找出字符串中所有的异位字符串

题目链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题目解析：再s字符串中找出p字符串中的所有异位字符串

异位字符串就是相同字符但是字符的顺序不一样组成的字符串，如abc、acb、bac、bca、cab和cba都是abc的异位字符串。

解决思路：滑动窗口+哈希表

如何判断两个字符串互为异位字符串呢？

第一种方法：我们可以将两个字符串按字典的顺序进行排序，接着判断这两个字符串是否相同就行，如果相同，那么就是异位字符串，如果不同，则不是异位字符串。

第二种方法：借用两个哈希表，hash1来存储p字符串，hash2来存储s字符串，最终判断两个哈希表是否相同，如果相同，那么互为异位字符串，如果不同，则不是异位字符串。

以下图为例

我们在s中找p的异位字符串，我们使用暴力枚举时，第一次枚举时，当right-left+1长度为p.length()时，第一次枚举就结束了，如下图

此时第一次枚举就结束了，进行第二次枚举，让left++，同时让right返回到left的所处的位置

进行第二次枚举时，right继续走向right-left+1=p.length()的位置，此时发现right依然会进过之前的字符b和字符a

所以，每一次进行新的枚举，没必要让right回到left的位置，这样left和right都是同向双指针，这时，我们就可以用滑动窗口来解决问题。

进窗口：当right-left+1<=s.length时，hash2[in]++

判断+出窗口

如果right-left+1>p.length()，就出窗口，让hash2[out]--，同时让left++

更新结果

要判断是异位字符串在更新结果

代码实现

//时间复杂度：O(n+m)
//空间复杂度：O(n+m)
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret=new ArrayList<>();
        char[] s=ss.toCharArray();
        char[] p=pp.toCharArray();
        int[] hash1=new int[26];
        int[] hash2=new int[26];
        for(char ch:p){
            hash1[ch-'a']++;
        }
        for(int left=0,right=0;right<s.length;right++){
            char in=s[right];
            hash2[in-'a']++;//进窗口
            if(right-left+1>p.length){//判断
                char out=s[left];
                hash2[out-'a']--;//出窗口
                left++;
            }
            //更新结果
            if(right-left+1==p.length){//判断是否互为异位字符串
                boolean flag=true;
                for(int i=0;i<26;i++){
                    if(hash1[i]!=hash2[i]){
                        flag=false;
                    }
                }
                if(flag==true)  ret.add(left);//更新结果
            }
        }
        return ret;
    }

进一步优化，此时我们可以在更新结果那里优化一下，因为在更新结果那里我们需要遍历两个哈希表，时间复杂度还是太大了，我们可以通过一个变量count统计窗口中的有效字符个数。

下图解释了什么是有效字符，一次类推

前面我们用hash1统计了字符串p中的情况，用hash2统计了字符串s中的情况。

进窗口之后，我们对hash1[in]和hash2[in]进行比较，如果hash2[in]小于等于hash1[in]，那么此时就可以认为该字符是一个有效字符，让count++

出窗口之前，我们对hash1[out]和hash2[out]进行比较，如果hash2[out]小于等于hash[out],此时就可以认为出去的字符是一个有效字符，让count--

最终在更新结果的时候，我们只要判断count是否等于p.length，如果等于p.length，就更新结果，如果不等于p.length，就不更新结果。

代码实现

       public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret=new ArrayList<>();
        char[] s=ss.toCharArray();
        char[] p=pp.toCharArray();
        int[] hash1=new int[26];
        int[] hash2=new int[26];
        for(char ch:p){
            hash1[ch-'a']++;
        }
        for(int left=0,right=0,count=0;right<s.length;right++){
            char in=s[right];
            hash2[in-'a']++;//进窗口
            if(hash2[in-'a']<=hash1[in-'a']) count++;//更新有效字符个数
            if(right-left+1>p.length){//判断
                char out=s[left];
                if(hash2[out-'a']<=hash1[out-'a']) count--;//更新有效字符个数
                hash2[out-'a']--;//出窗口
                left++;
            }
            //更新结果
            if(count==p.length) ret.add(left);
        }
        return ret;
    }

7.串联所有单词的子串

题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）

我们如果将words的每一个字符串看成一个整体，在以这个整体为单位去在s中找串联所有单词的子串，这时就跟找异位字符串差不多了。如下图

这道题的思路和第6题的解题思路差不多，这里讲不同点，假设words数组字符串的长度为m，数组的长度为len

1.right和left指针的位移

right和left一次位移的长度为m

2.hash表的不同

这里的哈希表存的是字符串的种类和数量，即Hash<String,Integer>

3.进行滑动窗口的次数

次数为m次

这里对不同点3进行解释

代码实现：

    public List<Integer> findSubstring(String s, String[] words) {
        Map<String,Integer> hash1=new HashMap<String,Integer>();//存储words
        List<Integer> ret=new ArrayList<Integer>();
        for(String str:words){
            hash1.put(str,hash1.getOrDefault(str,0)+1);
        }
        int len=words[0].length(), m=words.length;
        for(int i=0;i<len;i++){
            //执行滑动窗口
            Map<String,Integer> hash2=new HashMap<String,Integer>();//存储s
            for(int left=i,right=i,count=0;right+len<=s.length();right+=len){
                String in=s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in)<=hash1.getOrDefault(in,0)) count++;
                //判断+出窗口
                while(right-left+1>m*len){
                    String out=s.substring(left,left+len);
                    if(hash2.get(out)<=hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.getOrDefault(out,0)-1);
                    left+=len;
                }
                //更新结果
                if(count==m) ret.add(left);
            }
        }
        return ret;
    }

8.最小覆盖子串

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

题目分析：我们需要再字符串s中找一个子串，在这个子串中的字符种类，需要包含字符串t中所有字符类型，如果t中有了重复的字符，那么从s中找的子串的该字符的数量必须大于等于t中的重复字符的数量。

比如t为aba，那么在s中找的子串中，字符a的数量是不能小于t中a的字符数量。

解题思路：

首先，我们还是想到暴力枚举+hash表，我们将字符串中s的字符都枚举一遍，在枚举的过程中，如果遇到符合题目要求的子串，此时，就更新结果，接着立刻换一个字符进行新的枚举，以此类推下去。

优化思路：滑动窗口

如下图

此时，我们需要让left往后移动一步，当left++之后，left和right之间就会出现两种情况。

第一种情况：

如果left++之后，left和right之间的字符种类没有发生变化，当我们让right回到left的位置，进行新的枚举时，right还是会回到原来的位置。如下图

第二种情况：

如果left++之后，left和right之间的字符种类发生变化，当我们让right回到left的位置时，进行新的枚举，为了找到新的符合题目要求的子串，此时right肯定时跑到原来位置的后面。如下图：

所以，我们发现没必要每次都要将right返回到原来left的位置，我们只要根据每次left移动后的情况，根据情况来让right不动或者往后移动。

此时，发现left和right都是同向双指针，此时就可以使用滑动窗口。

在使用滑动窗口前，我们要用到两个哈希表，一个用来存储s字符串的情况，另一个用来存储t字符串的情况。

进窗口：hash2[in]++

判断+更新结果+出窗口：

判断：在s中找的子串是否符合题目要求，也就是hash2与hash1对应字符的数量是否一样

跟新结果：由于我们这里找到一个符合题目要求的子串就要跟新结果，所以此处的跟新结果实在出窗口之前

出窗口：hash2[out]--

在进一步优化：更新结果

在更新结果那里，我们需要遍历两个哈希表来判断找的子串是否符合题目要求，每个哈希表都要遍历一遍，时间复杂度还是太大了，此时，我们可以通过count变量来统计hash1和hash2中完全相同的字符数量。

这里的完全相同是指数量和种类都相同。

在进窗口之后，如果hash2[in]==hash1[in],那么，我们认为在in在hash1和hash2中是完全相同的字符，则让count++

出窗口之前，如果如果hash2[in]==hash1[in],那么，我们认为在in在hash1和hash2中是完全相同的字符，则让count--

此时判断条件就变为count==hash1.size().

代码实现：

    public String minWindow(String ss, String tt) {
        char[] s=ss.toCharArray();
        char[] t=tt.toCharArray();
        int[] hash1=new int[128];//存储t
        int[] hash2=new int[128];//存储s;
        int kinds=0;//记录t中有效字符的种类
        for(char ch:t){
            if(hash1[ch]==0) kinds++;
            hash1[ch]++;
        }
        int minlen=Integer.MAX_VALUE, begin=-1;
        for(int left=0,right=0,count=0;right<s.length;right++){
            //进窗口
            char in=s[right];
            hash2[in]++;
            if(hash2[in]==hash1[in]) count++;
            //判断+更新+出窗口
            while(kinds==count){
                //更新结果
                if(right-left+1<minlen){
                    minlen=right-left+1;
                    begin=left;
                }
                //出窗口
                char out=s[left];
                if(hash2[out]==hash1[out]) count--;
                hash2[out]--;//出窗口
                left++;//维护窗口
            }
        }
        if(begin==-1) return new String();
        else return ss.substring(begin,begin+minlen);
    }