优选算法的时序之窗：滑动窗口专题(一)

专栏算法的魔法世界个人主页手握风云目录一、滑动窗口二、例题讲解2.1. 长度最小的子数组2.2. 无重复字符的最长子串2.3. 水果成篮2.4. 将 x 减到 0 的最小操作一、滑动窗口滑动窗口算法又叫“同向双指针算法”核心在于维护一个窗口这个窗口的左右边界可以根据需要动态调整。窗口的大小通常取决于当前窗口内的元素是否满足某种条件。通过移动窗口的左右边界可以在一次遍历中找到满足条件的子数组或子串。二、例题讲解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-left1); 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-left1);//更新结果 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) { MapInteger,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-left1); } 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; } }