算法笔记：滑动窗口

电玩女神 2024-03-26 12:56 42阅读 0赞

### 1 滑动窗口 ###

`滑动窗口`就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。主要用于处理连续的数组数据或者字符串数据，常用来提取数据中的子数组或者子串。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将时间复杂度为O(n2)的暴力解法降为O(n)。

### 2 例题 ###

**题目描述**

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

找出该数组中满足其和 `≥ target` 的长度最小的 **连续子数组** `[numsl, numsl+1, ..., numsr-1, numsr]` ，并返回其长度\*\*。\*\*如果不存在符合条件的子数组，返回 `0` 。

**示例**

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

**题目来源**

*  [209. 长度最小的子数组 - 力扣（Leetcode）][209. _ - _Leetcode]

### 2 解法 ###

#### 2.1 暴力解法 ####

##### 2.1.1 解题思路 #####

暴力解法，两层遍历（leetcode上有一份非常非常长的数组数据，运行会超时）

时间复杂度：O(n2)

##### 2.1.2 Java 代码实现 #####

public static int minSubArrayLen(int target, int[] nums) {
        
        // 存储结果，初始化为整型最大值
        int result = Integer.MAX_VALUE;
        // 逐个遍历
        for (int i = 0; i < nums.length; i++) {
        
            // 存储总和
            int sum = 0;
            // 存储子数组长度
            int res = 0;
            // 题干是连续子数组，所以从当前值往后逐个遍历
            for (int j = i; j < nums.length; j++) {
        
                // 累加元素值
                sum += nums[j];
                // 累加子数组长度
                res++;
                // 子数组长度超过当前最小结果，直接break
                if (res >= result) {
        
                    break;
                }
                // 总和大于或等于目标值，将子数组长度赋给结果值
                if (sum >= target) {
        
                    result = res;
                    break;
                }
            }
        }
        // 如果结果值没有被赋值过，说明数组中没有符合条件的子数组，返回0
        return result == Integer.MAX_VALUE ? 0 : result;
    }

#### 2.2 滑动窗口 ####

##### 2.2.1 解题思路 #####

滑动窗口，定义两个指针 start 和 end 分别表示子数组（滑动窗口）的开始位置和结束位置

每一轮迭代，将 end 右移到子数组和 sum 满足条件，然后减去 start 的值，再将 start 右移一位，开始新的迭代，迭代过程记录更新子数组的最小长度

时间复杂度：O(n)

##### 2.2.2 图解滑动窗口过程 #####

![请添加图片描述][e1353b05fa9c40b6aff06214325fc9d3.gif]

##### 2.2.3 Java 代码实现 #####

public static int minSubArrayLen(int target, int[] nums) {
        
        int start = 0;
        // 存储子数组元素总和
        int sum = 0;
        // 存储结果，初始化为整型最大值
        int result = Integer.MAX_VALUE;
        for (int end = 0; end < nums.length; end++) {
        
            sum += nums[end];
            while (sum >= target) {
        
                // 子数组长度，取较小值
                result = Math.min(result, end - start + 1);
                // 减去开始位置元素，滑动窗口右移
                sum -= nums[start];
                // start指针右移
                start++;
            }
        }
        // 如果结果值没有被赋值过，说明数组中没有符合条件的子数组，返回0
        return result == Integer.MAX_VALUE ? 0 : result;
    }

**代码逻辑小总结**

1.  外层 for 循环完成结束位置指针的遍历；
2.  for 循环内部 while 循环的条件为满足开始位置指针移动的条件，while 循环内需要移除开始位置指针的元素并将开始位置指针右移。

### 3 相关题目（题目来源：Leetcode） ###

#### 3.1 水果成篮 ####

##### 3.1.1 题目描述 #####

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 `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] 这五棵树。

**题目来源**

*  [904. 水果成篮 - 力扣（Leetcode）][904. _ - _Leetcode]

##### 3.1.2 解题思路 #####

> 滑动窗口，使用哈希表存储水果类型及水果数量
> 
> 使用end指针遍历所有果树，每次遍历将水果类型对应数量加1
> 
> 当水果类型超过两种，滑动窗口内的值不符合条件，将start指针的水果类型对应的数量减1，如果数量等于0，则将该水果类型从哈希表中移除，start指针右移

##### 3.1.3 Java 代码实现 #####

public int totalFruit(int[] fruits) {
        
        int start = 0;
        int result = 0;
        // 使用哈希表存储水果类型及水果数量
        Map<Integer, Integer> basket = new HashMap<>();
        for (int end = 0; end < fruits.length; end++) {
        
            // 存储水果类型，将水果数量加1
            basket.put(fruits[end], basket.getOrDefault(fruits[end], 0) + 1);
            // 当水果类型超过两种，滑动窗口内的值不符合条件，start指针右移
            while (basket.size() > 2) {
        
                // 将start指针的水果类型对应的数量减1，如果数量等于0，则将该水果类型从哈希表中移除
                basket.put(fruits[start], basket.get(fruits[start]) - 1);
                if (basket.get(fruits[start]) == 0) {
        
                    basket.remove(fruits[start]);
                }
                // start指针右移
                start++;
            }
            // 返回滑动窗口长度的最大值
            result = Math.max(result, end - start + 1);
        }
        return result;
    }

#### 3.2 最小覆盖子串 ####

##### 3.2.1 题目描述 #####

给你一个字符串 `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 的子串中，
    因此没有符合条件的子字符串，返回空字符串。

**题目来源**

*  [76. 最小覆盖子串 - 力扣（Leetcode）][76. _ - _Leetcode]

##### 3.2.2 解题思路 #####

> 滑动窗口
> 
> 使用两个哈希表，分别存储需要的字符及数量和窗口内的字符及数量；再定义左右指针以及一个符合条件的字符数量变量；
> 
> 右指针遍历字符串，当前字符如果是需要的，则对窗口哈希表内对应字符数量+1；
> 
> 当符合条件的字符数量等于需要的字符哈希表的长度时，说明当前子串满足条件，记录下较小的子串；
> 
> 此时左指针的字符若是需要的，则对窗口哈希表内对应字符数量-1，然后左指针右移，继续循环

##### 3.2.3 Java 代码实现 #####

public String minWindow(String s, String t) {
        
        // 需要的字符及对应数量
        Map<Character, Integer> needCharMap = new HashMap<>();
        // 滑动窗口的字符及对应数量
        Map<Character, Integer> winCharMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
        
            needCharMap.put(t.charAt(i), needCharMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0;
        // 存储结果串的长度，初始为整型最大值
        int length = Integer.MAX_VALUE;
        // 存储结果串
        String result = "";
        // 符合条件的字符数
        int num = 0;
        for (int right = 0; right < s.length(); right++) {
        
            if (needCharMap.containsKey(s.charAt(right))) {
        
                winCharMap.put(s.charAt(right), winCharMap.getOrDefault(s.charAt(right), 0) + 1);
                // 当滑动窗口内字符数量等于需要的字符串对应字符的数量时，该字符符合条件，num加一
                // 注：只有在等于的时候才需要对num加一，后续窗口内字符数量是有可能超过所需字符数量的，避免重复累加
                if (winCharMap.get(s.charAt(right)).equals(needCharMap.get(s.charAt(right)))) {
        
                    num++;
                }
            }
    
            while (num == needCharMap.size()) {
        
                if (length > right - left + 1) {
        
                    result = s.substring(left, right + 1);
                    length = right - left + 1;
                }
                if (needCharMap.containsKey(s.charAt(left))) {
        
                    winCharMap.put(s.charAt(left), winCharMap.get(s.charAt(left)) - 1);
                    // 当滑动窗口内字符数量小于t字符串对应字符的数量时，该字符不再符合条件，num减一
                    if (winCharMap.get(s.charAt(left)) < needCharMap.get(s.charAt(left))) {
        
                        num--;
                    }
                }
                left++;
            }
        }
        return length == Integer.MAX_VALUE ? "" : result;
    }

[209. _ - _Leetcode]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[e1353b05fa9c40b6aff06214325fc9d3.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ded7f639572544599173c344248c5cc6.png
[904. _ - _Leetcode]: https://leetcode.cn/problems/fruit-into-baskets/
[76. _ - _Leetcode]: https://leetcode.cn/problems/minimum-window-substring/