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

   

专栏：算法的邪术天下

  

个人主页：手握风云

  目录
一、滑动窗口
二、例题解说
2.1. 长度最小的子数组
2.2. 无重复字符的最宗子串
2.3. 水果成篮
2.4. 将 x 减到 0 的最小操作
一、滑动窗口

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

2.1. 长度最小的子数组

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

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

。

代码实现：

1. class Solution{
2.     public int minSubArrayLen(int target,int[] nums){
3.         int sum = 0,len = Integer.MAX_VALUE,
4.         for(int left = 0,right = 0; right < nums.length; right++){
5.             sum += nums[right];//进窗口
6.             while(sum >= target){
7.                 len = Math.min(len,right-left+1);
8.                 sum -= nums[left++];
9.             }
10.         }
11.         return len == Integer.MAX_VALUE ? 0 : len;//如果给定的数组和小于目标值，直接返回0
12.     }
13. }

复制代码

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

       第一种解法，使用暴力枚举，即找出所有不含重复字符的子串，再比较长度大小。那我们如何知道字符重复出现呢？我们在这里可以使用哈希表，同样是界说两个指针left和right，让right把遍历过的字符扔进哈希表内里，此时我们就需要遍历两遍子串，时间复杂度为

。

       当right遇到重复的字符时，left向右移动。按照暴力枚举的策略，right还需要回来，再次向右移动，这是没有必要了。因为left与right之间还有与right指向相同的字符，那么left指针此时就可以直接跳过了。由于两个指针也是同向移动的，就可以使用滑动窗口来办理。
       滑动窗口的办理过程就是“进窗口→判断→出窗口→更新结果”。“进窗口”就是将字符扔进哈希表中；“判断”的过程就是看看哈希表中是否存在重复的字符；“出窗口”就是从哈希表中删除重复的字符。
        完整代码实现：

1. class Solution{
2.     public int lengthOfLongestSubstring(String s){
3.         char[] str = s.toCharArray();//将字符串转化为字符数组
4.         int hash = new int[128];//用数组模拟哈希表
5.         int left = 0,right = 0,n = s.length;
6.         int ret = 0;
7.         while(right < n){
8.           hash[ss[right]]++;//进入窗口
9.           while (hash[ss[right]] > 1){//判断
10.               hash[ss[left++]]--;//出窗口
11.           }
12.           ret = Math.max(ret,right-left+1);//更新结果
13.           right++;//让下一个字符进入窗口
14.         }
15.         return ret;
16.     }
17. }

复制代码

2.3. 水果成篮

        题目中给出我们只有两个篮子，每个篮子只能装一种水果，可以从任意一棵树开始，中间不能越过某一棵树，求收集的水果的最大数量。我们看下面的测试用例，我们可以采摘[0,1]两棵树，也可以采摘[1,2,2]三棵树。也就是题目要求我们求出给定数组的最宗子数组，并且子数组中只含有两种数字。

        我们如何知道子数组内里只有两种水果，可以使用哈希表来存储水果的种类数量。我们取出一段子数组，内里的水果种类kinds恰恰为2，此时让left向右移动，会出现两种结果：kinds不变，right也不需要向右移动；kinds减小，则right向右移动，让子数组中的水果种类再次增加为2。

        通过上面的示例分析，我们可以得出双指针是通向移动的，还是使用滑动窗口来办理问题。“进窗口”，把水果扔进哈希表中。“判断”，当哈希表的长度大于2时，那么这个窗口不是合法的，就得让left向右移动。但我们不知道left需要移动到那里，那我们的哈希表就不能只界说一个元素种类，还有一个元素的数量。然后“出窗口”，把哈希表里的元素删除，让窗口变得合法。

        完整代码实现：

1. class Solution {
2.     public int totalFruit(int[] fruits) {
3.         Map<Integer,Integer> hash = new HashMap<>();//统计窗口内的水果种类
4.         int ret = 0;
5.         for (int left = 0,right = 0;right < fruits.length;right++){
6.             int in = fruits[right];
7.             hash.put(in,hash.getOrDefault(in,0)+1);//进窗口
8.             while(hash.size() > 2){
9.                 int out = fruits[left];
10.                 hash.put(out,hash.get(out)-1);//出窗口
11.                 if(hash.get( out) == 0){
12.                     hash.remove(out);
13.                 }
14.                 left++;
15.             }
16.             ret = Math.max(ret,right-left+1);
17.         }
18.         return ret;
19.     }
20. }

复制代码

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指针向左移动，完成“出窗口”的操作；末了更新结果，找到最长的子数组。
        完整代码实现：

1. class Solution {
2.     public int minOperations(int[] nums, int x) {
3.         int sum = 0,len = nums.length;
4.         for (int i = 0; i < len; i++) {
5.             sum += nums[i];
6.         }//求总数组的和
7.         int target = sum - x;
9.         if(target < 0) return -1;
11.         int ret = -1;
12.         for (int left = 0,right = 0,tmp = 0;right < len;right++){
13.             tmp += nums[right];//进窗口
14.             while(tmp > target)//判断
15.                 tmp -= nums[left++];//出窗口
16.             if(tmp == target)
17.                 ret = Math.max(ret,right - left + 1);//更新结果
18.         }
19.         if(ret == -1) return ret;
20.         else return len - ret;
21.     }
22. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。