滑动窗口算法专题（1）

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏： 优选算法专题

目录

滑动窗口算法的简介

209. 长度最小的子数组

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

1004. 最大连续1的个数III

1658. 将×减到0的最小操作数

滑动窗口算法的简介

滑动窗口算法本质上就是双指针算法的一个衍生版本。

这个就是类似双指针算法里的快慢指针。但是快慢指针一般用去求序列的长度或是中间位置等问题，且快慢指针的速度一般都是固定的。但是滑动窗口算法中的 left指针和 right指针移动是根据题目的要求进行的。

滑动窗口算法的步骤也是固定的，即有自己固定的套路。一般步骤如下：

1、初始化窗口：left = 0，right = 0；

2、 扩大窗口：right++；

3、判断题目的要求。

接下来就是根据 第三步的结果来进行不同的处理。

如果满足题目要求，就继续扩大窗口的大小，再进行判断。即重复2、3步骤。如果不满足题目要求就得更新结果，再缩小窗口，接着再去判断是否满足题目要求，即循环判断是否满足题目要求。

滑动窗口算法广泛应用于数组和字符串等序列中求子序列的问题。例如：求子数组、子字符串等。

上面就是简介的全部了。

下面就开始实战。

209. 长度最小的子数组

题目： 

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的子数组（可以去原题看解释）

  [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度 。如果不存在符合条件的子数组，返回  0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

思路： 首先想到的就是去遍历数组，找出不同的长度，然后比较找出最小值即可。

最暴力的解法就是枚举每一个数组元素的对应长度的值，最终最短的路径一定是在这些值里面的。

代码实现：

错误解法（暴力枚举）：

class Solution {
    // 暴力枚举
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int right = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int left = 0;
        while (right < nums.length) {
            // 首先得计算sum的值
            sum += nums[right];
            // 再判断sum 和 target的大小关系
            if (sum < target) {
                right++;
            } else {
                // 将长度，入堆，再继续往后走
                minHeap.add(right-left+1);
                right = ++left;
                sum = 0;
            }
        }
        // 小根堆可能为空，得判断
        return minHeap.isEmpty() == true ? 0 : minHeap.peek();
    }
}

上面代码去运行时，会超出时间限制。但是有一个让我很疑惑的地方。如下所示：

我个人认为是这个后台在跑一个测试用例时，能通过；但是全部一起跑的时候，最终的叠加时间超出了时间限制。 

接下来就得开始进行优化。上面的代码有一个地方时发生了重复计算的：当我们找出符合条件的子区间时，不应该从头继续开始，我们上面的做法是跳过left所在的元素，继续往后遍历寻找。但是有一个更优的方法：直接让left++不就行了吗。这就节约了继续跑的时间。

但有小伙伴可能会疑惑：有没有可能漏掉了值呢？答案是不可能的。现在right所在的位置是上一次满足条件的位置，并且这个位置是加上left才满足的，因此去掉left之后，在[left+1，right)的位置肯定不会满足条件的。因此我们可以大胆的去做。

但是可能在去掉 left 之后，还可能继续大于 target，因此这里我们可以加上一个循环判断直至小于target。

优化解法： 

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        while (right < nums.length) {
            sum += nums[right];
            // 满足条件，就一直更新并缩小窗口
            while (sum >= target) {
                minHeap.add(right-left+1);
                sum -= nums[left++];
            }
            // 走到这里说明sum < target
            right++;
        }
        return minHeap.isEmpty() ? 0 : minHeap.peek();
    }
}

上面的代码的效率还不是最优，因为我们使用堆这个数据结构来存储和计算最小长度。这个时间可不能忽略。因此下面就是不使用堆的做法。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        // 这里不能是0，求最小值时会有影响
        int len = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right];
            // 满足条件，就一直更新并缩小窗口
            while (sum >= target) {
                len = Math.min(len, right-left+1);
                sum -= nums[left++];
            }
            // 走到这里说明sum < target
            right++;
        }
        // 可能while循环没进入，len的值还是int最大值
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

下面就来分析一下，滑动窗口的做法：

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

题目：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串（可以去原题看解释） 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

思路： 这里要我们找不重复的最长子串。首先看到不重复，我们就应该想到用哈希表来解决。那么这里的暴力枚举思路也就出来了。直接遍历字符串，找到一个字符，看其是否在哈希表中。如果在，则从下一个位置开始遍历；反之，则将其加入哈希表，继续往后遍历。

代码实现： 

暴力枚举版本（能通过，但效率低下）：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        Map<Character, Integer> hash = new HashMap<>();
        int count = 0;
        int len = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            // 看哈希表中是否出现过这个元素
            if (hash.getOrDefault(ch, 0) == 0) {
                // 没出现就添加，再继续遍历
                hash.put(ch, 1);
                right++;
                count++;
            } else {
                // 记录最长子串的长度，并更行count
                len = Math.max(count, len);
                count = 0;
                // right从头开始，哈希表中的元素也得清除
                right = ++left;
                hash.clear();
            }
        }
        // 可能出现没有重复的现象或者未被更新
        len = Math.max(count, len);
        return len;
    }
}

 这个代码的思想总体上和上一题的暴力枚举是一样的。出现了重复的字符，就从left+1的位置继续开始遍历。上一题在处理这种情况时，是我们了解了在right位置之前不会出现这种情况，所以我们可以直接让left++。但是在这里即使left++了也不一定能跳过重复的字符。

优化后的版本： 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        Map<Character, Integer> hash = new HashMap<>();
        int count = 0;
        int len = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            // 看哈希表中是否出现过这个元素
            if (hash.getOrDefault(ch, 0) == 0) {
                // 没出现就添加，再继续遍历
                hash.put(ch, 1);
                right++;
                count++;
            } else {
                // 判断是否还有重复的元素
                while (hash.getOrDefault(ch, 0) != 0) {
                    len = Math.max(len, count); // 更新长度
                    hash.remove(ch); // 删除元素(不一定是重复的)
                    count--; // 计数器--
                    ch = s.charAt(left++); // 遍历找寻重复的元素
                }
            }
        }
        // 同样也可能全部是不重复的
        len = Math.max(len, count);
        return len;
    }
}

 但这个还不是最优的版本。由于我们使用了哈希表这个数据结构，在查询和删除时，都需要浪费一些时间。因此最优的版本就是使用数组来模拟哈希表。

最优版本：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int[] hash = new int[128]; // 根据ASCII码表来指定
        int count = 0;
        int len = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            // 看哈希表中是否出现过这个元素
            if (hash[ch] == 0) {
                // 没出现就添加，再继续遍历
                hash[ch]++;
                right++;
                count++;
            } else {
                // 判断是否还有重复的元素
                while (hash[ch] != 0) {
                    len = Math.max(len, count); // 更新长度
                    hash[ch]--; // 删除元素(不一定是重复的)
                    count--; // 计数器--
                    ch = s.charAt(left++); // 遍历找寻重复的元素
                }
            }
        }
        // 同样也可能全部是不重复的
        len = Math.max(len, count);
        return len;
    }
}

这个最优版本就是用数组模拟实现了哈希表而已，并没有其他的多余变化。 

从这里我们也可以得出一个结论：能够自己手动的模拟实现该数据结构的功能，尽量可以手动实现，这不仅可以提升时间效率，而且在面试的时候，还能让面试官对我们另眼相看。

1004. 最大连续1的个数III

题目：

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1
• 0 <= k <= nums.length

注意：这个题目一定不能去修改对应位置为1，那样根本就解不出来。此次修改对应位置的值之后，拿下一次还得还原并且将另外的位置进行修改。因此这种修改对应位置的题目，一般是采用一个计数器来进行逻辑修改，从而实现最终的解题。 

思路：题目的要求就是让我们找到数组中连续1的最大长度。即在序列中寻找符合要求的子序列。这就是用滑动窗口算法来解决。首先考虑暴力枚举的方法。从 left 为0的位置开始往后遍历，遇到1，right++，遇到0，计数器++。当计数器的长度等于k时，就得停下来了，计算此时序列的长度。然后再从left+1的位置开始继续遍历，直至序列遍历完成。接下来就要去优化了。如下所示：

代码实现：

这里就不再给出暴力枚举的代码，大家可以自行实现(参照上面的暴力枚举)：

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int right = 0;
        int len = 0;
        int count = 0;
        while (right < nums.length) {
            if (nums[right] == 1) { // 继续走
                right++;
            } else { // 判断0的个数是否符合要求
                if (count < k) {
                    count++;
                    right++; // 还能继续走
                } else {
                    // 此时right的位置并非合法位置
                    len = Math.max(len, right-left);
                    while (nums[left] == 1) { // 要跳过0
                        left++;
                    }
                    // 此时left对应的位置为0
                    left++;
                    count--;
                }
            }
        }
        // 可能会出现没有统计len的情况，即count<k一直满足
        len = Math.max(len, right-left);
        return len;
    }
}

1658. 将×减到0的最小操作数

题目：

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

思路：读完题，如果从正面直接去写，根本没有丝毫的思路。从上面给的示例也可以看出：左边突然使用一下，接着又是右边突然使用一下，这根本没有任何的规律和逻辑。因此我们得从反面来写，题目是让我们找出长度最小的一段或者多段连续的序列的和刚好等于x（序列必须来自最左边或者最右边）。我们完全可以按照下面的方式来处理：

因此，这里题目就转换成了寻找一段连续的最长的序列其和的值为sum-x即可。这里就是用到滑动窗口的算法步骤来解决。

代码实现：

class Solution {
    public int minOperations(int[] nums, int x) {
        // 计算出要寻找的目标值
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        int target = sum - x;
        // 当target小于0时，肯定不可能找到（数组元素全部是大于0的）
        if (target < 0) {
            return -1;
        }
        // 找出最长的序列长度
        int left = 0;
        int right = 0;
        sum = 0;
        int len = -1; // 这里不能是0，可能后面更新的结果是0
        while (right < nums.length) {
            sum += nums[right];
            if (sum < target) {
                right++; // 继续往后寻找
            } else { // sum >= target
                while (sum > target) {
                    sum -= nums[left];
                    left++;
                }
                if (sum == target) {
                    len = Math.max(len, right-left+1); // 记录此时的长度
                }
                // 这里避免死循环造成left越界
                right++;
            }
        }
        // 要么计算出来了值，要么啥也没有
        return len == -1 ? -1 : nums.length-len; 
    }
}

注意：这里len的初始化一定不能是0。因为当len是0，并且target == sum 时，最后就会导致left与right一直是指向同一个位置，即两者算出的长度为0，但是我们最后再判断时，输出的结果是-1；而我们想要的结果是 nums.length。因此这里一定不能初始化为0。

总结：这一题算是这四个题目中最难的一个。思路就不是正常人可以想到的，即使想到了之后，后面的一些细节问题的处理也是需要我们正常人去反复调试对比的，根本不是一次就能AC的。这道题难度还是非常大的。 

好啦！本期 滑动窗口算法专题（1）的学习之旅 就到此结束啦！我们下一期再一起学习吧！