算法训练计划--------滑动窗口

前言：

????????Hello，大家好，我是Go。本文将呈现笔者本人最近在做的滑动窗口算法题。记录一下笔者学习到的题解思路以及附上个人代码，供大家参考及指正。希望对正在学习算法，尤其是滑动窗口算法的同学提供一点帮助。

---

滑动窗口算法：

? ? ? ? 滑动窗口算法换言之就是 left 和 right 指针同向运动的双指针算法。当 left 和 right 指针的同向运动，限定出一块 连续的区间，我们可以在区间内维护和更新结果时，此算法就是滑动窗口算法。

俗话说?Talk is cheap. Show me the code。我们话不多说，直接上题让大家亲身感受一下。

---

实战训练：

一、LeetCode：209.长度最小的子数组（Medium）

思路：

1、 根据题目的描述和实例的展示，我们可以分析出。我们要分析的是nums中一段连续的区间，判断 区间和 >= target 的最小区间。所以我们可以利用滑动窗口算法解决问题。

2、首先定义两个指针 left = 0 ,right = 0，sum = 0（记录窗口内元素的和）。

每次，先将right指针所在位置元素相加。sun += nums[right]。并判断sum是否大于等于target

每当大于等于 target。就代表?[left,right-1] 此区间的元素和满足条件，那么我们就更新结果。并且窗口缩小（出窗口），也就 left++ 去下一个窗口寻找满足条件的区间。

小于target的话，代表区间元素和不满足条件，需要继续扩大窗口，也就是 right++。

拿示例一：【2，3，1，2，4，3】举例。区间内元素为 2 3 1 2 时，sum=8 > target。

此时能满足条件的最小区间便是 2 3 1 2。那么此时以2为基准的窗口已经没用了，那么我们就可以将窗口滑动，以3为基准找到满足条件的最小区间。于是找到 3 1 2 4 这个窗口。循环往复直到 r >?nums.length-1

图解：

代码：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0,r = 0,n = nums.length,min = n+1,sum=0;
        while(r<n){
            //进窗口
            sum += nums[r];
            while(sum>=target){
                //判断，更新长度
                min = Math.min(min,r-l+1);
                //出窗口 窗口向右缩减
                sum-=nums[l++];
            }
            //窗口向右扩张
            r++;
        }
        //如果min大于n 表示没有符合的区间，返回0
        return min>n ? 0 : min;
    }

}

二、LeetCode：3.无重复字符的最长子串（Medium）

思路：

1、从题目可看出，我们分析的是字符串中，连续的无重复的最长区间，所以便可以想到利用滑动窗口。同时为了保证无重复字符（或者说是每个字符只出现一次），就需要哈希表来记录每个字符出现的次数。保证字符唯一

2、定义 left = 0 , right = 0;每次右端字符ch，进入窗口时，都将其放入哈希表中查看出现的次数。

如果该字符存在过（即哈希表key对应的value>1），就缩小窗口，寻找不存在重复字符的区间。

如果该字符没存在过，则代表此区间无重复字符，更新结果。随后继续扩大窗口

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //将字符串转换成字符数组
        char[] ss = s.toCharArray();
        //使用数组模拟哈希表
        int[] hash = new int[128];
        int l = 0,r = 0,max =0,n =ss.length;
        while(r<n){
            //入窗口，并在对应处设置哈希值
            hash[ss[r]]++;
            //判断
            while(hash[ss[r]]>1){
                //将左端点的数据删除，并出窗口
                hash[ss[l++]]--;
            }
            max = Math.max(max,r-l+1);
            r++;
        }
        return max;
    }
}

三、LeetCode：1004.最大连续1的个数（Medium）

思路：

1、不用真正的将0进行翻转，我们可以把问题转化成：求数组中?段最?的连续区间，要求这段区间内 0 的个数不超 过 k 个。关乎到连续区间，那我们就可以用滑动窗口

2、设置 left = 0,right = 0。zero = 0 用来统计0出现的次数。窗口向右扩张。遇到0，zero++。

每当zero>k时。我们先要判断窗口左端是否为0；是0，出窗口后则zero--，及时更新0的数量。不是0，则窗口缩减，不做任何事。

如果0的数量不大于k，那么我们就要对结果进行更新。

代码：

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l =0,r = 0,max = 0, zero = 0, n=nums.length;
        while(r<n){
            //入窗口 判断元素是否为0
            if(nums[r]==0) zero++;
            while(zero>k){
                if(nums[l]==0) zero--;//更新0的个数
                //出窗口
                l++;
            }
            //更新结果
            max = Math.max(max,r-l+1);
            r++;
        }
        return max;
    }
}

四、LeetCode：1658.将X减到0的最小操作数 （Medium）

思路：

1、本道题初看非常难下手。但我们转变一下思路。nums的元素和arraySum?与 目标值x 是固定的。此时我们需要找的是，数组中是否有一块连续的区域，元素和等于 arraySum - x。如果有，则返回剩下的数组长度，没有则返回 -1 即可。那么我们便使用滑动窗口。

2、设置 left = 0,right = 0。每次循环，加上最右端的值，将窗口中的元素和 跟 arraySum-x比较。

如果 元素和 >?arraySum-x，就要缩减窗口，寻找合适的值。

如果 元素和 ==?arraySum-x，我们就更新一次结果，直到 right = nums.length-1。

图解：

代码：

class Solution {
    public int minOperations(int[] nums, int x) {
        int sum = 0;
        //求出数组元素和
        for(int y:nums){
            sum+=y;
        }

        //如果 sum - x 小于0。代表数组里的数不满足条件
        int target = sum-x;
        if(target<0) return -1;

        int max = -1,n=nums.length;
        for(int l=0,r=0,flag = 0;r<n;r++){
            //进窗口
            flag+=nums[r];//记录窗口内元素和
            while(flag>target){
                //出窗口
                flag-=nums[l++];
            }
            //如果flag == target 更新结果
            if(flag == target) max = Math.max(max,r-l+1);
        }
        //max 没有变动表示数组内没有满足条件的数
        if(max == -1) return -1;
        return n-max;
    }
}

?五、LeetCode：904.水果成篮

1、分析题目，要求我们在只能拥有至多两种水果的情况下，能收集到的最大水果数。换言之，要找的是一段 不能有第三个其他数的最长连续区间。所以我们可以用滑动窗口解决。

2、设置 left = 0, right =0 。为了保证种类限定在两种或以下，我们用哈希表，key记录果树种类，value记录此树的果子数。并用变量kinds记录树的种类。每次循环先判断此种果树是否摘过。

没摘过，就更新哈希表，并且kinds++。记录已摘了一种类型的水果。摘过，则果数（value）++。

并且对kinds进行判断。

如果kinds>2，表示此时窗口内果树种类过大，那么此时就缩减窗口。并且缩减窗口时判断，减去的果树，果子数量是否为0，为0表示这种类型的果树已不需要，更新果树种类，kinds--。

如果 kinds <=2，都表示窗口内的数据是合法的，就更新数据。

代码：

class Solution {
    public int totalFruit(int[] fruits) {
        //利用数组模拟哈希
        int n = fruits.length;
        int[] hash = new int[n+1];

        int max = 0;
        for(int l=0,r=0,kinds=0;r<n;r++){
            //判断该种类是否存在
            int in = fruits[r];
            //进窗口
            if(hash[in]==0) kinds++;//不存在，种类加一
            hash[in]++;
            while(kinds>2){
                //出窗口
                int out = fruits[l];
                hash[out]--;
                if(hash[out]==0) kinds--;//种类减少
                l++;
            }
            //kinds<=2时，更新结果
            max = Math.max(max,r-l+1);
        }
        return max;

    }
}

六、LeetCode：438.找到字符串中所有字母异位词（Medium）

思路：

代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //利用数组模拟哈希 p字符哈希
        char[] pp = p.toCharArray();
        int[] phash  = new int[26];
        for(char ch :pp){
            //将目标字符串所含字符存入哈希
            phash[ch-'a']++;
        }
        
        //窗口内字符的哈希
        char[] ss =s.toCharArray();
        int[] shash = new int[26];
        List<Integer> ans = new ArrayList<>();
        int n =ss.length,m=pp.length,count = 0;
        for(int l=0,r=0;r<n;r++){
            //进窗口
            char in =  ss[r];
            shash[in-'a']++;
            //进完窗口，如果在该字符对应的hash位置。shash<=phash。代表此字符是有效字符
            if(shash[in-'a']<=phash[in-'a']) count++;//计数器加一
            //限定窗口大小
            if(r-l+1>m){
                char out = ss[l];
                //出窗口前判断该字符是否为有效字符
                if(shash[out-'a']<=phash[out-'a']) count--;
                //出窗口
                shash[out-'a']--;
                l++;
            }
            //当有效字符数等于p的字符个数，更新结果
            if(count == m) ans.add(l);
        }
        return ans;
    }
}

七、LeetCode：30.串联所有单词的子串（Hard）

思路：

1、?如果我们把每?个单词看成?个?个字?，问题就变成了找到「字符串中所有的字?异位词」。??就是之前处理的对象是?个?个的字符，我们这?处理的对象是?个?个的单词。

本题笔者能力有限，凭借文章是很难将完整的思路进行讲述。当时笔者也是经过许多次error，费了挺多时间才解决。固此只提供代码，大家可以凭借思路及代码，还有官方题解自行体会，十分抱歉！

代码：

class Solution {
    public List<Integer> findSubstring(String s, String[] p) {
        List<Integer> ans = new ArrayList<>();
        //先将字典数组的字符串装入hash之中
        HashMap<String,Integer> phash = new HashMap<String,Integer>();
        for(String str:p){
            //先判断是否存在
            phash.put(str,phash.getOrDefault(str,0) + 1);
        }
        int len = p[0].length(),m=p.length;
        //滑动窗口运动次数(从不同的位置开始，获取所有可能的结果)
        //重点理解此处!画图模拟模拟!
        for(int i=0;i<len;i++){
            //创建遍历数组的哈希表
            HashMap<String,Integer> shash = new HashMap<String,Integer>();
            for(int l =i,r=i,count=0;r+len<=s.length();r+=len){
                //进窗口
                String in = s.substring(r,r+len);
                shash.put(in,shash.getOrDefault(in,0)+1);
                //判断是否为有效字符
                if(shash.get(in)<=phash.getOrDefault(in,0)) count++;

                //限定窗口大小
                if(r-l+1>m*len){
                    String out = s.substring(l,l+len);
                    //先判断
                    if(shash.get(out)<=phash.getOrDefault(out,0)) count--;
                    //出窗口
                    shash.put(out,shash.get(out)-1);
                    l+=len;
                }
                //当有效字符串跟字典长度一致时 更新结果
                if(count == m) ans.add(l);
            }
        }
        return ans;
    }
}

八、LeetCode：76.最小覆盖子串（Hard）?

思路：

1、研究的对象同样是一段连续的区间，判断s字符串种是否有一段最短的连续的区间，包含了所给t字符串中的所有字符。?

2、本题的思路其实跟438题（本文第六题）的思想大致一样。只在一些其他方面有所不同：

提供数据：本题提供的字符串 s 和 t 都是由英文字母（大写或小写）构成！而非只有小写。

窗口大小方面：本题的窗口非固定的，但窗口大小一定要 >= 所给字符 t 的长度。

返回结果：本题返回的是s中满足条件的一段子串，所以涉及子串的起始位置。

代码：

class Solution {
    public String minWindow(String s, String t) {
        char[] tt = t.toCharArray();
        char[] thash = new char[128];
        int kinds = 0;
        for(char ch:tt){
            if(thash[ch]++ == 0) kinds++;
        }
        
        char[] ss =s.toCharArray();
        char[] shash = new char[128];
        int n = s.length(),start = -1,min = Integer.MAX_VALUE;
        for(int l = 0,r=0,count=0;r<n;r++){
            //进窗口
            char in = ss[r];
            shash[in]++;
            //判断字符是否有效
            if(shash[in] == thash[in]) count++;
            while(count==kinds){
                //更新结果
                if(r-l+1<min){
                    start = l;
                    min = r-l+1;
                }
                char out = ss[l++];
                if(shash[out] == thash[out]) count--;
                //出窗口
                shash[out]--;
            }
        }
        if(start == -1) return "";
        else return s.substring(start,start+min);//注意substring是左闭右开的形式

    }
}

---

结语：

????????本次滑动窗口算法过程分享便到此！本人的实力尚低，算法知识尚浅！思路和代码方面，如果有疏忽和纰漏！劳请大家多多指正！希望本文可以帮助大家！一起进步！