经典算法之——滑动窗口

- 日理万妓 2023-10-10 23:55 22阅读 0赞

![在这里插入图片描述][4d1a431593c94d68ab92d8eff2392411.webp_pic_center]

#### 文章目录 ####

*  前言
 *  基本思路
 *  基本模板
 *  例题
 *   *  一、 定窗口滑动
     *  二、变化窗口
     *   *  方法一：暴力枚举
         *  方法二：队列--双指针法
         *  方法三、二分窗口

--------------------

## 前言 ##

`滑动窗口算法是较为入门题目的经典算法之一`，一般是一些有规律数组问题的最优解，如果一个数组的问题可以用动态规划解，但又可以使用滑动窗口解决，那么往往滑动窗口的效率更高。

`而关于双指针的算法中，它的左右指针则是形成了一个窗口`  
双指针也并不局限在数组问题，像链表场景的 “快慢指针” 也属于双指针的场景，其快慢指针滑动过程中本身就会产生一个窗口，而这样的话就很容易形成一种变化的滑动窗口，当然也会有定向窗口大小。

`而在计算机网路中则存在滑动窗口协议:`该协议是 TCP协议 的一种应用，用于网络数据传输时的流量控制，以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认。因此该协议可以加速数据的传输，提高网络吞吐量。

滑动窗口算法其实和这个是一样的，只是用的地方场景不一样，所以掌握这种算法的技巧在编程中也是很重要的。

## 基本思路 ##

（1）`初始化窗口:`  
初始化左右边界 left = right = 0，把索引闭区间 \[left, right\] 称为一个「窗口」。

（2）`寻找可行解：`  
我们先不断地增加 right 指针扩大窗口 \[left, right\]，直到窗口中的满足可行解。

（3）`优化可行解：`  
此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 \[left, right\]，直到窗口中的可行解不再符合要求。同时，每次增加 left，我们都要更新一轮结果。

（4）`滑动窗口，直至一次遍历结束：`  
重复第 2 和第 3 步，直到 right 到达到的尽头。

## 基本模板 ##

public void slideWindowTemplate(String nums){
        
        int l = 0, r = 0;        //[初始化窗口]
        //codes...               [其他初始化信息,定义一些维护数据的数据结构]
        while(r < nums.length){
         //右边框移动
            r++;                 //[增大窗口]
            //codes.....         [更新窗口中的数据] 
            while(l < r && check(xxx) == false){
           //[窗口不满足某种性质]
                  l++;             //[缩小窗口]
                //codes...       [维护窗口中的数据]
            }
        }
    }

--------------------

`到这里就以几道题目作为引导说明:`

## 例题 ##

### 一、 定窗口滑动 ###

**返回窗口大小为3且平均数大于等于子数组数目5**

`说明：`  
i 的范围只能从下标0到（array.lenght-1)-k,而j的范围可以从0到array.lenght-1，就这样形成一个为k的大小窗口，左为i，右为j=i+3

--------------------

![在这里插入图片描述][013b633fe49f4346917ba73547355fdb.png]

static int sum;
        static int res;
        public static void main(String[] args) {
        
            int[] array={
        11,13,17,23,29,31,7,5,2,3};
            sum=0;res=0;
            numOf(array,3,5);
            System.out.println(res);
        }
        private static void numOf(int[] array,int k,int threshold){
        
             for(int i=0;i<= array.length-k;i++){
        //确定左边界
                 for(int j=i;j<i+k;j++){
         //在这个窗口的大小从左边界向右移动k格
                     sum+=array[j];
                 }
                 if(sum>=threshold*k) ++res;
                 sum=0;
             }
        }

### 二、变化窗口 ###

`就拿变化滑动窗口来说明一下其实滑动窗口问题还有其他的解法`  
**例题：和满足SUM且长度最小的子数组并返回大小**

#### 方法一：暴力枚举 ####

`说明：`  
先定义L=0，然后判断是否大于了SUM，如果大于就返回；没有的话就从第二个数据相加并至后一直判断，完成L=0，r遍历完成之后，然后L向右移动一个，继续r=L+1开始继续遍历;当L到最后一个格子的时候就完成任务了。Math.min(min, r-l + 1)用来找出窗口最小又大于SUM值的  
![在这里插入图片描述][ebd15c94732f4b54918915deffff3931.png]

public int minSubArrayLen(int SUM, int[] nums) {
        
            int min = Integer.MAX_VALUE; //先定义最小为整形的最大值
            for (int l = 0; l < nums.length; l++){
        
                int sum = nums[i];
                if (sum >= SUM)
                    return 1;
                for (int r = l + 1; r < nums.length; r++) {
        
                    sum += nums[r];
                    if (sum >= SUM) {
        
                        min = Math.min(min, r-l + 1);//r-l + 1 为右边框-左边框=窗口的大小
                        break;
                    }
                }
            }
            return min == Integer.MAX_VALUE ? 0 : min;
        }

#### 方法二：队列–双指针法 ####

`说明：`  
利用队列的思路，用两个指针的指向头和尾；先把全部的数据进行加入到队列中，然后再根据条件删减前面数据。  
![在这里插入图片描述][ecd5514c219f401f883c89922f5f2369.png]

public int minSubArrayLen(int target, int[] nums){
        
    int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE;
            while(hi < nums.length){
        
                sum+=nums[hi++];
                while(sum >= target){
         //可能我们所加最后一个数过大，前面的数小了，可以减去前面
                   min = Math.min(min, hi - lo); //hi - lo 为右边框-左边框=窗口的大小
                    sum -= nums[lo++];
                }
            }
            return min == Integer.MAX_VALUE ? 0 : min;
    }

#### 方法三、二分窗口 ####

`说明：`  
利用二分的思想，先将窗口进行check()，如果满足>=SUM的话需要进行缩小窗口，大于的话就进行扩大

public int minSubArrayLen(int s, int[] nums) {
        
            int lo = 0, hi = nums.length-1, min = 0;
            while (lo <= hi) {
        
                int mid = lo+((hi-lo) >> 1); // 二分窗口
                if (windowExist(mid, nums, s)) {
         //根据是否需要扩大或者缩小窗口
                    hi = mid - 1;//找到就缩小窗口的大小
                    min = mid;//如果找到就记录下来
                } else
                    lo = mid + 1;//没找到就扩大窗口的大小
            }
            return min;
        }
    
        //size窗口的大小
        //这个大小窗口的数和无法满足>=s返回FALSE,或者可以满足则返回ture
        private boolean windowExist(int size, int[] nums, int target){
         
            int sum = 0;
            for(int i = 0; i < nums.length; i++){
        
                if (i >= size){
        //如果加到超过了该位置的窗口大小还没有满足条件，就进行向右移动
                  sum-=nums[i - size]; 
                }
                sum += nums[i];
                if(sum >= target)
                    return true;
            }
            return false;
        }

--------------------

**ok~ 滑动窗口先讲到这里，后续有什么补充我再进行添加**

[4d1a431593c94d68ab92d8eff2392411.webp_pic_center]: https://img-blog.csdnimg.cn/4d1a431593c94d68ab92d8eff2392411.webp#pic_center
[013b633fe49f4346917ba73547355fdb.png]: https://img-blog.csdnimg.cn/013b633fe49f4346917ba73547355fdb.png
[ebd15c94732f4b54918915deffff3931.png]: https://img-blog.csdnimg.cn/ebd15c94732f4b54918915deffff3931.png
[ecd5514c219f401f883c89922f5f2369.png]: https://img-blog.csdnimg.cn/ecd5514c219f401f883c89922f5f2369.png