前言
滑动窗口算法是较为入门题目的经典算法之一，一般是一些有规律数组问题的最优解，如果一个数组的问题可以用动态规划解，但又可以使用滑动窗口解决，那么往往滑动窗口的效率更高。
而关于双指针的算法中，它的左右指针则是形成了一个窗口
双指针也并不局限在数组问题，像链表场景的 “快慢指针” 也属于双指针的场景，其快慢指针滑动过程中本身就会产生一个窗口，而这样的话就很容易形成一种变化的滑动窗口，当然也会有定向窗口大小。
而在计算机网路中则存在滑动窗口协议:该协议是 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
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值的
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; }
方法二：队列–双指针法
说明：
利用队列的思路，用两个指针的指向头和尾；先把全部的数据进行加入到队列中，然后再根据条件删减前面数据。
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~ 滑动窗口先讲到这里，后续有什么补充我再进行添加
