【刷题笔记】之滑动窗口（长度最小的子数组、水果成篮、最小的覆盖子串）

滑动窗口模板

//滑动窗口模板：注意使用滑动窗口方法，使用一个 for(while) 循环中的变量是用来控制终止位置的//最小滑窗：给定数组 nums，定义滑动窗口的左右边界 i、j，求满足某个条件的滑窗的最小长度
for(j = 0; j < nums.length; ++j) {不断的添加值到题中要求的结果集中(比如 sum)while(满足条件) {更新求最小长度 result = Math.min(result,j-i+1);不断更新结果集(比如 sum)i++; // 缩小左边界}
}//最大滑窗：给定数组 nums，定义滑窗的左右边界 i、j，求满足某个条件的滑窗的最大长度
for(j = 0; j < nums.length; ++j) {不断的添加值到题中要求的结果集中(比如 sum)while(不满足条件) {i++; // 缩小左边界不断更新结果集(比如 sum)}// 走到这里条件满足，更新最小长度，继续 for 循环更新求最小长度 result = Math.min(result,j-i+1);
}

1. 长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

给定一个含有 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

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思想：

滑动窗口就是不断的调节子序列的起始位置和终止位置，从而得出想要的结果

使用暴力解法，是一个 for 循环滑动窗口的起始位置，一个 for 循环为滑动窗口的终止位置，用两个 for 循环完成一个不断搜索区间的过程。

而滑动窗口是用一个 for 循环来完成这个操作，并且这个 for 表示的应该是终止位置

因为，如果这个 for 表示的是起始位置，那么如何遍历剩下的终止位置呢，到最后还是又回到了暴力解法

所以 滑动窗口，使用一个 for 循环来表示滑动窗口的终止位置

使用滑动窗口需要确定三点：

窗口内是什么？
窗口就是满足 sum >= targe 长度的最小的连续子数组
如何移动窗口的起始位置
起始位置就是 如果当前窗口的值大于 targe，窗口就要向前移动了（缩小范围）
如何移动窗口的结束位置
结束位置就是 for 循环中的索引

滑动窗口的优点在于能够根据当前子序列和大小的情况，不断调节子序列的起始位置，在这道题中也就是满足sum >= target 时起始位置就要开始移动，从而将 O(n^2) 暴力解法时间复杂度降为 O(n)

滑动窗口

    // 209public int minSubArrayLen(int target, int[] nums) {int i = 0; //左int result = Integer.MAX_VALUE;int sum = 0;for (int j = 0; j < nums.length; j++) { // 右sum += nums[j];while(sum >= target) { // while 循环找到满足要求且元素个数最小的result = Math.min(result,j-i+1);sum -= nums[i++];}}return result == Integer.MAX_VALUE ? 0 : result;}

2. 水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。

你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。

一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

1 <= fruits.length <= 105

0 <= fruits[i] < fruits.length

思想：

在上一题长度最小的子数组中是要求满足条件的子数组的最小长度，用滑动窗口的方法来说，就是最小滑窗是在迭代右移左边界的过程中更新结果。

而本道题水果成篮是要求满足条件情况下收集水果的最大数目，也就是要在迭代右移右边界的过程中更新结果。

利用 left 和 right 分别表示窗口的左右边界，同时利用哈希表来存储这个窗口内的数以及出现的次数，一个 for 循环控制的就是终止位置也就是右边界，右移一个位置，并且将 fruits[right] 加入到哈希表中，如果 哈希表大小大于2（也就是水果的种类），那就移动 left 将 fruits[left] 从哈希表中移除，直到满足要求，并且当 fruits[left] 在哈希表中出现的次数减少为0，那就将 key 移除

代码：

public int totalFruit(int[] fruits) {int n = fruits.length;Map<Integer,Integer> cnt = new HashMap<>();int left = 0, ans = 0;for(int right = 0; right < n; ++ right) {// 每次添加一个水果计数cnt.put(fruits[right],cnt.getOrDefault(fruits[right],0) + 1);// 如果添加新水果后，不止两种，就从前往后逐渐丢弃水果while(cnt.size() > 2) {int pre = fruits[left++];cnt.put(pre,cnt.get(pre) - 1);// 如果这种水果被全部丢弃，就从 map 中删除if(cnt.get(pre) == 0) {cnt.remove(pre);}}// 计算一下当前区域的长度ans = Math.max(ans,right-left+1);}return ans;
}

3. 最小的覆盖子串

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length

• n == t.length

• 1 <= m, n <= 105

• s 和 t 由英文字母组成

**进阶：**你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

思想：

还是按滑动窗口的思路来做

1. 不断增加 j 使滑动窗口增大，直到窗口包含了 T 中所有元素

2. 不断增加 i 使用滑动窗口缩小，因为是要求最小子串，所以要将不必要的元素排除在外，使用长度减小，直到遇到一个必须包含的元素，那么此时就记录这个滑动窗口的长度，并且保存最小值（也就是保存左边界，然后可以根据长度计算右边界，从而可以返回子串）

3. 让 i 再向右移动一个位置，那么这个时候滑动窗口肯定是不满足条件的，就重新从步骤1 开始执行，寻找新的满足条件的滑动窗口

判断滑动窗口中包含了 T 的所有元素

这里可以用一个字典 need 也就是数组来表示滑动窗口中需要的各个元素的数量，int[] need = new int[128] 这个数组大小设为 128 是因为 ascii 中有 128 个字符，比如 need[76] = 2，表示 ascii 为 76 的这个字符，在字符串中需要两个，比如 need[76] = -2，表示 ascii 为 76 的这个字符，在字符串中多余两个。

先把用 T 把 need 数组初始化，表示现在need[X] = ? 需要这些元素，下面就是通过滑动窗口来修改need 数组中的元素，当滑动窗口中包含某个元素，就让 need 元素减1，代表需要的元素减1，当滑动窗口移除某个元素，就让 need 中元素的数量加1，这样做的目的就是为了步骤2中的 排除不必要元素，数量为负表示不必要元素，数量为 0 表示刚刚好

need 数组中记录着当前滑动窗口中，需要的元素数量，这个动态修改是靠滑动窗口的移动来维护的

总之，如何判断滑动窗口中包含了 T 的所有元素，这是根据 need 中所有元素的数量都小于或等于 0 时，表示当前滑动窗口不需要任何元素

但是还有个细节，每次判断滑动窗口是否包含 T 的所有元素，都是去判断 need 所有元素数量都小于等于0，这样还是要遍历 need 的，这个是要耗费时间的，所以可以**定义一个变量 needCnt 来记录当前需要元素的总数量，**当遇到所需元素 c，那 need[c] 就减1，同时 needCnt 也减1，这样就不用每次都来遍历 need 数组了，只需要看 needCnt 就行

代码：

public String minWindow(String s, String t) {// need 数组表示每个字符在 t 中需要的数量// need[76]=2 表示 ascii为76的字符在目标字符串中需要两个int[] need = new int[128];// 用 t 来初始化 need 【初始状态】for(int i = 0; i < t.length(); i++) {need[t.charAt(i)]++;}/*left/right: 窗口左右边界size: 表示窗口的长度needCnt: 表示当前所需字符的总数，起始大小为 t 的长度start：表示有效窗口的起始位置，可以根据size，来求子串区间范围*/int left = 0, size = Integer.MAX_VALUE, needCnt = t.length(), start = 0;for(int right = 0; right < s.length(); right++) {char c = s.charAt(right);// 【步骤一】// 如果当前这个字符 c 在 t 中存在那么 need 中对应位置应该是大于 0if(need[c] > 0) {needCnt--;  // 找到一个元素了，所需字符总数-1}// 不论这个字符是否在 t 中都要 -1.need[c]--;if(needCnt == 0) {// 【步骤二】// 缩小左边界，去除无用的元素while(left < right && need[s.charAt(left)] < 0) {need[s.charAt(left)]++;left++;}// 更新窗口的长度if(right - left + 1 < size) {size = right - left + 1;start = left;}// 【步骤三】need[s.charAt(left)]++;left++;needCnt++;}}return size == Integer.MAX_VALUE ? "" : s.substring(start,start+size);
}