优选算法的智慧之光：滑动窗口专题(一)

专栏：算法的魔法世界

个人主页：手握风云

一、滑动窗口

二、例题讲解

2.1. 长度最小的子数组

2.2. 无重复字符的最长子串

2.3. 水果成篮

2.4. 将 x 减到 0 的最小操作

一、滑动窗口

滑动窗口算法又叫“同向双指针算法”，核心在于维护一个窗口，这个窗口的左右边界可以根据需要动态调整。窗口的大小通常取决于当前窗口内的元素是否满足某种条件。通过移动窗口的左右边界，可以在一次遍历中找到满足条件的子数组或子串。

二、例题讲解

2.1. 长度最小的子数组

题目要求找出长度最小的子数组，并且子数组的和大于等于目标值。暴力枚举策略，就是找出所有和大于等于目标值的子数组，我们需要找出子数组的左右区间，还要遍历一遍子数组求和，那么时间复杂度为 $O(n^{3})$ 。

接下来对暴力枚举进行优化。题目中给出了条件，数组里的元素都是正整数。我们可以定义两个指针left和right，让right向右移动，left和right就可以构成一个子数组。当子数组的和大于等于目标值时就固定，让left指针也向右移动。因为数组是具有单调性的，两个指针不用回退，就可以省去很多不必要的枚举，让子数组里的元素不停进出，维护更新子数组的和。我们操作只有right和left的移动，那么时间复杂度为 $O(n)$ 。

代码实现：

java">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把遍历过的字符扔进哈希表里面，此时我们就需要遍历两遍子串，时间复杂度为 $O(n^{2})$ 。

当right遇到重复的字符时，left向右移动。按照暴力枚举的策略，right还需要回来，再次向右移动，这是没有必要了。因为left与right之间还有与right指向相同的字符，那么left指针此时就可以直接跳过了。由于两个指针也是同向移动的，就可以利用滑动窗口来解决。

滑动窗口的解决过程就是“进窗口→判断→出窗口→更新结果”。“进窗口”就是将字符扔进哈希表中；“判断”的过程就是看看哈希表中是否存在重复的字符；“出窗口”就是从哈希表中删除重复的字符。

完整代码实现：

java">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需要移动到哪里，那我们的哈希表就不能只定义一个元素种类，还有一个元素的数量。然后“出窗口”，把哈希表里的元素删除，让窗口变得合法。

完整代码实现：

java">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指针向左移动，完成“出窗口”的操作；最后更新结果，找到最长的子数组。

完整代码实现：

java">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;}
}