优选算法的时序之窗：滑动窗口专题(一)
专栏：算法的魔法世界
个人主页：手握风云
目录
一、滑动窗口
滑动窗口算法又叫“同向双指针算法”，核心在于维护一个窗口，这个窗口的左右边界可以根据需要动态调整。窗口的大小通常取决于当前窗口内的元素是否满足某种条件。通过移动窗口的左右边界，可以在一次遍历中找到满足条件的子数组或子串。
二、例题讲解
2.1. 长度最小的子数组
题目要求找出长度最小的子数组，并且子数组的和大于等于目标值。暴力枚举策略，就是找出所有和大于等于目标值的子数组，我们需要找出子数组的左右区间，还要遍历一遍子数组求和，那么时间复杂度为
。
接下来对暴力枚举进行优化。题目中给出了条件，数组里的元素都是正整数。我们可以定义两个指针left和right，让right向右移动，left和right就可以构成一个子数组。当子数组的和大于等于目标值时就固定，让left指针也向右移动。因为数组是具有单调性的，两个指针不用回退，就可以省去很多不必要的枚举，让子数组里的元素不停进出，维护更新子数组的和。我们操作只有right和left的移动，那么时间复杂度为
。
代码实现：
class Solution{ public int minSubArrayLen(int target,int[] nums){ int sum = 0,len = Integer.MAX_VALUE, for(int left = 0,right = 0; right < nums.length; right++){ sum += nums[right];//进窗口 while(sum >= target){ len = Math.min(len,right-left+1); sum -= nums[left++]; } } return len == Integer.MAX_VALUE ? 0 : len;//如果给定的数组和小于目标值，直接返回0 } }2.2. 无重复字符的最长子串
第一种解法，使用暴力枚举，即找出所有不含重复字符的子串，再比较长度大小。那我们如何知道字符重复出现呢？我们在这里可以使用哈希表，同样是定义两个指针left和right，让right把遍历过的字符扔进哈希表里面，此时我们就需要遍历两遍子串，时间复杂度为
。
当right遇到重复的字符时，left向右移动。按照暴力枚举的策略，right还需要回来，再次向右移动，这是没有必要了。因为left与right之间还有与right指向相同的字符，那么left指针此时就可以直接跳过了。由于两个指针也是同向移动的，就可以利用滑动窗口来解决。
滑动窗口的解决过程就是“进窗口→判断→出窗口→更新结果”。“进窗口”就是将字符扔进哈希表中；“判断”的过程就是看看哈希表中是否存在重复的字符；“出窗口”就是从哈希表中删除重复的字符。
完整代码实现：
class Solution{ public int lengthOfLongestSubstring(String s){ char[] str = s.toCharArray();//将字符串转化为字符数组 int hash = new int[128];//用数组模拟哈希表 int left = 0,right = 0,n = s.length; int ret = 0; while(right < n){ hash[ss[right]]++;//进入窗口 while (hash[ss[right]] > 1){//判断 hash[ss[left++]]--;//出窗口 } ret = Math.max(ret,right-left+1);//更新结果 right++;//让下一个字符进入窗口 } return ret; } }2.3. 水果成篮
题目中给出我们只有两个篮子，每个篮子只能装一种水果，可以从任意一棵树开始，中间不能越过某一棵树，求收集的水果的最大数目。我们看下面的测试用例，我们可以采摘[0,1]两棵树，也可以采摘[1,2,2]三棵树。也就是题目要求我们求出给定数组的最长子数组，并且子数组中只含有两种数字。
我们如何知道子数组里面只有两种水果，可以利用哈希表来存储水果的种类数量。我们取出一段子数组，里面的水果种类kinds恰好为2，此时让left向右移动，会出现两种结果：kinds不变，right也不需要向右移动；kinds减小，则right向右移动，让子数组中的水果种类再次增加为2。
通过上面的示例分析，我们可以得出双指针是通向移动的，照样使用滑动窗口来解决问题。“进窗口”，把水果扔进哈希表中。“判断”，当哈希表的长度大于2时，那么这个窗口不是合法的，就得让left向右移动。但我们不知道left需要移动到哪里，那我们的哈希表就不能只定义一个元素种类，还有一个元素的数量。然后“出窗口”，把哈希表里的元素删除，让窗口变得合法。
完整代码实现：
class Solution { public int totalFruit(int[] fruits) { Map<Integer,Integer> hash = new HashMap<>();//统计窗口内的水果种类 int ret = 0; for (int left = 0,right = 0;right < fruits.length;right++){ int in = fruits[right]; hash.put(in,hash.getOrDefault(in,0)+1);//进窗口 while(hash.size() > 2){ int out = fruits[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; } }2.4. 将 x 减到 0 的最小操作数
对于上面的测试用例，我们可以移除“1、1、3”，此时操作数是3次；我们也可以移除“3、2”，此时的最小操作数为2。如果我们直接想这道题会非常困难，因为我们不知道是先删左边还是先闪右边。那如果我们反过来思考，从数组当中找出一段最长的子数组，这个最长子数组的和target就是给定数组的和sum减去x的值。
我们先定义两个指针left和right，当right指针移动到某个下标时，子数组的和小于sum,如果right再向右移动一位，此时恰好target大于等于sum。之后我们再让left指针向右移动，此时我们需要思考一下，right是否需要回退？是不需要的（如下图所示），right要么不动，要么向右移动，此时又符合同向双指针的解法，也就是可以使用滑动窗口。
“进窗口”，right指针向右移动，计算子数组的和；“判断”，当子数组的和大于target时（这里不写等于，是为了防止代码书写混乱的），left指针向左移动，完成“出窗口”的操作；最后更新结果，找到最长的子数组。
完整代码实现：
class Solution { public int minOperations(int[] nums, int x) { int sum = 0,len = nums.length; for (int i = 0; i < len; i++) { sum += nums[i]; }//求总数组的和 int target = sum - x; if(target < 0) return -1; int ret = -1; for (int left = 0,right = 0,tmp = 0;right < len;right++){ tmp += nums[right];//进窗口 while(tmp > target)//判断 tmp -= nums[left++];//出窗口 if(tmp == target) ret = Math.max(ret,right - left + 1);//更新结果 } if(ret == -1) return ret; else return len - ret; } }
