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

布满荆棘的人生 2023-09-25 15:50 48阅读 0赞

## 滑动窗口模板 ##

//滑动窗口模板：注意使用滑动窗口方法，使用一个 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);
    }

![dd5fb3f298cefcc6da9eef74d46d167f.png][]

## 1. 长度最小的子数组 ##

**题目链接：**[209. 长度最小的子数组 - 力扣（LeetCode）][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)**

### 滑动窗口 ###

// 209
        public 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）][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）][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 中所有元素**

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

1.  让 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 就行

![ab761e17236016f7bd579d971c683a0f.png][]

### 代码： ###

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 中对应位置应该是大于 0
            if(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);
    }

[dd5fb3f298cefcc6da9eef74d46d167f.png]: https://img-blog.csdnimg.cn/img_convert/dd5fb3f298cefcc6da9eef74d46d167f.png
[209. _ - _LeetCode]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[904. _ - _LeetCode]: https://leetcode.cn/problems/fruit-into-baskets/
[76. _ - _LeetCode]: https://leetcode.cn/problems/minimum-window-substring/
[ab761e17236016f7bd579d971c683a0f.png]: https://img-blog.csdnimg.cn/img_convert/ab761e17236016f7bd579d971c683a0f.png