【寻找one piece的算法之路】滑动窗口

💐个人主页：初晴~

📚相关专栏：寻找one piece的刷题之路

什么是滑动窗口

滑动窗口算法是一种常用的算法模式，通常用于字符串匹配、数组操作等问题中，特别是需要在一段连续的数据中寻找满足特定条件的子序列问题。它通过维护一个窗口（一段连续的子数组或子串），并在数据结构上滑动（移动）这个窗口，来寻找最优解或者满足特定条件的子序列。

滑动窗口算法的基本步骤

1. 初始化窗口：选择一个起始点，并确定窗口的初始大小。
2. 扩展窗口：从起始点开始，向右扩展窗口，直到找到一个满足特定条件的子序列。
3. 收缩窗口：如果当前窗口的子序列仍然满足条件，尝试从左侧收缩窗口，直到不满足条件为止。
4. 更新结果：在每次扩展和收缩窗口之后，检查当前窗口是否是最优解，并更新结果。
5. 重复步骤：重复上述步骤，直到遍历完整个输入数据。

滑动窗口算法的优点

• 效率高：相比暴力解法，滑动窗口算法可以在O(n)的时间复杂度内解决问题，其中n是输入数据的长度。
• 易于实现：算法逻辑简单，易于理解和实现。
• 适用性广：可以应用于多种不同类型的问题。

一、⻓度最⼩的⼦数组

题目链接

题目描述：

题目分析：

因为这题计算的是某一段区间的元素总和，是连续的，就可以尝试用滑动窗口来解决。每次固定好左指针l，然后让右指针r 不断向右遍历数组，并记录累加和sum，直到第一次区间【l，r】的sum>target时，我们就找到了以 l 为起始点的最大窗口，接着就没必要再继续向右扩展窗口了。此时就可以尝试舍去l，让l向右移动，缩小窗口，由于我们已经知道区间【l，r】的元素和了，就没必要再遍历计算一遍了。将sum减去之前 l 所指的元素值，就能得到区间【l+1，r】的元素和了。以此类推，我们只要不断维护好这个区间就能得出最终结果了

滑动流程：

1、初始化窗口：定义两个指针 l 和 r ，一开始都让他们指向0位置

2、扩展窗口：让 r 指向的元素“进入窗口”

3、收缩窗口：判断此时窗口内元素和与target大小关系

• 如果大于等于：更新结果，将左端元素划出去的同时继续判断是否满⾜条件并更新结果（因为左端元素可能很⼩，划出去之后依旧满⾜条件）
• 如果小于：说明窗口太小，  right++ ，另下⼀个元素进⼊窗⼝

4、重复步骤：重复上述步骤2与3，直到 指针r 遍历完整个输入数据

代码实现：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n=nums.length,min=Integer.MAX_VALUE,sum=0;
        for(int l=0,r=0;r<n;r++){
            sum+=nums[r];  //进窗口
            while(sum>=target){ //判断
                min=Math.min(min,r-l+1);//更新结果
                sum-=nums[l++]; //滑动窗口
            }
        }
        return min==Integer.MAX_VALUE?0:min;
    }
}

二、无重复字符的最长子串

题目链接

题目描述：

题目分析：

可以定义一个长度为128的数组作为简易hash表，来存储某一区间的元素种类

由于这题研究的对象依然是一段连续的区间，因此可以使用滑动窗口来解决。维护窗口内元素不出现重复即可

滑动流程：

1、初始化窗口：定义两个指针 l 和 r ，一开始都让他们指向0位置

2、扩展窗口：让 r 指向的元素“进入窗口”，哈希表统计这个字符的频次

3、收缩窗口：判断此次进入窗口的字符出现的频次：

• 如果超过1：说明窗口内存在重复元素，此时不断将左端元素划出窗口，直到该字符出现的频次变成1
• 如果没有超过1：说明当前窗口没有重复元素，不需要收缩窗口

5、重复步骤：重复上述步骤2、3、4，直到 指针 r 遍历完整个输入数据

代码实现：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] hash=new int[128]; //数组模拟哈希表
        char[] sc=s.toCharArray();
        int n=s.length(),max=0,l=0,r=0;
        while(r<n){
            hash[sc[r]]++;   //进入窗口
            while(hash[sc[r]]>1){ //查重
                hash[sc[l++]]--;  //出窗口
            }
            max=Math.max(max,r-l+1); //更新结果
            r++; //让下一个字符进入窗口
        }
        return max;
    }
}

三、最大连续1的个数

题目链接

题目描述：

题目分析：

不用把问题想的非常复杂，去思考该如何翻转0，没有必要，我们可以直接把这题看成是往一堆连续的1中插入了最多k 个0，这么一想就比较清晰了。

由于是连续区间，明显可以使用滑动窗口。我们只要维护一段窗口，保证窗口内0的个数不超过k即可。

滑动流程：

通过变量zero来维护窗口内0的个数

1、初始化窗口：定义两个指针 l 和 r ，一开始都让他们指向0位置

2、扩展窗口：让 r 指向的元素“进入窗口”，判断如果该元素为0，则让zero值加一

3、收缩窗口：判断此时窗口0的数量：

• 如果超过k：说明窗口内0的数量过多，此时不断将左端元素划出窗口，并实时记录zero，直到zero值小于等于k
• 如果没有超过k：说明当前窗口内0的个数符合要求，不需要收缩窗口

5、重复步骤：重复上述步骤2、3、4，直到 指针 r 遍历完整个输入数据

代码实现：

class Solution {
    public int longestOnes(int[] nums, int k) {
        int max=0;
        for(int zero=0,l=0,r=0;r<nums.length;r++){
            if(nums[r]==0)zero++;
            while(zero>k)  
                if(nums[l++]==0)zero--;
            max=Math.max(max,r-l+1);
        }
        return max;
    }
}

四、将 x 减到 0 的最⼩操作数

题目链接

题目描述：

题目分析：

题目本意是让我们求数组“左端和右端”两段连续的、和为x的最短数组。两段？如果想使用滑动窗口的话似乎就会非常复杂了。

不妨让我们把思路逆转，这不就是把一个数组切成了左中右三个部分嘛。左边与右边是断开的不好求，但中间一块都是连续的呀！于是我们可以将题目转化为求数组内一段连续的，和为sum(nums)-x的最长数组不就好了嘛。

这样一看，这与第一题不就妥妥的孪生兄弟嘛，用滑动窗口再合适不过了

滑之前的准备：

先遍历一遍给定数组，记录总的数组和target，接着让target减去x，作为接下来滑动窗口的目标值。由于这是整数数组，如果target<0，说明一定无解，直接返回-1即可。

滑动流程：

1、初始化窗口：定义两个指针 l 和 r ，一开始都让他们指向0位置

2、扩展窗口：不断让 r 指向的元素“进入窗口”，并更新元素和sum

3、收缩窗口：判断此时sum与target大小关系：

• 如果sum<target：说明现在窗口过小，不用收缩窗口
• 如果sum>target：说明当前窗口内元素和过大，需要收缩窗口，不断右移指针l，直到sum<=target为止

5、重复步骤：重复上述步骤2、3、4，直到 指针 r 遍历完整个输入数据

代码实现：

class Solution {
    public int minOperations(int[] nums, int x) {
        int n=nums.length,target=0,sum=0,max=-1;
        for(int i=0;i<n;i++){
            target+=nums[i];
        }
        target-=x; //将找两边问题转化为找中间
        if(target<0)return -1; //小优化
        for(int l=0,r=0;r<n;r++){
            sum+=nums[r]; //进窗口
            while(sum>target&&l<=r){ //判断
                sum-=nums[l++]; //出窗口
            }
            if(sum==target){ 
                max=Math.max(max,r-l+1); //更新结果
            }
        }
        return max==-1?-1:n-max;
    }
}

五、⽔果成篮

题目链接

题目描述：

题目分析：

由于研究对象是一段连续区间，于是可以尝试用滑动窗口来解决

维护窗口内元素满足只有两种水果作为条件即可。可以通过hash表来维护水果种类及出现频次。不过直接使用自带hash表的开销会比较大，我们可以用一个数组来模拟hash表

用数组下标作为水果种类，数组值作为对应水果数量。不过这样似乎就不好计算水果种类数了，该怎么办？我们可以再建立一个变量kinds，记录水果总量。每次滑动窗口，无非就是多一个或者少一个水果，因此我们可以再每次滑动时做判断,：

• 如果是增加一个水果，且对应水果数量由0变为1，相当于从无到有，水果种类肯定是变多的，我们就让kinds++
• 如果是减少一个水果，且对应水果数量由1变为0，相当于从有到无，水果种类肯定是变少的，我们就让kinds--

这样我们就通过一个变量kinds很方便的记录了水果种类数了。然后就可以开滑了

代码实现：

class Solution {
    public int totalFruit(int[] fruits) {
        
        int n=fruits.length,max=0;
        int[] hash=new int[n+1];
        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--;
            }
            max=Math.max(max,r-l+1);
        }
        return max;
    }
}

六、找到字符串中所有字⺟异位词

题目链接

题目描述：

题目分析：

由于子串的概念也是连续的，因此就可以尝试使用滑动窗口

由题意可知，字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量

当窗口内每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p 的异位词

滑之前的准备：

先将字符串p转化为字符数组cs1，接着遍历数组，通过⼤⼩为 26 的 target数组来存储字符串 p中每种字符的个数。不过直接判断两个数组是否相等的话会比较麻烦，于是我们可以通过一个变量count来记录两个的相同元素数，如果窗口长于字符串长度len相同，且count==len，就说明此时符合条件

代码实现：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] cs1=p.toCharArray(),cs2=s.toCharArray();
        int n=s.length(),len=p.length();
        int[] target=new int[26],hash=new int[26];
        for(char c:cs1){
            target[c-'a']++;
        }
        List<Integer> list=new ArrayList<>();
        for(int l=0,r=0,count=0;r<n;r++){
            int in=cs2[r];
            if(++hash[in-'a']<=target[in-'a'])count++;
            if(r-l+1>len){
                int out =cs2[l++];
                if(hash[out-'a']--<=target[out-'a'])count--;
            }
            if(count==len)list.add(l);
        }
        return list;
    }
}

那么本篇文章就到此为止了，如果觉得这篇文章对你有帮助的话，可以点一下关注和点赞来支持作者哦。如果有什么讲的不对的地方欢迎在评论区指出，希望能够和你们一起进步✊