【算法专项一】滑动窗口法

悠悠 2023-01-14 13:56 192阅读 0赞

# 简介 #

所谓滑动窗口法，又称为“寸取法”，一般用来解决**查找满足依一定条件的连续区间的特殊性质（长度等）** 等一类问题。

由于区间是连续的，因此当整个区间发生变化时，可以通过对旧有的计算结果对搜索空间的剪枝（一般就是滑动窗口最左侧滑出的部分），从而减少了重复计算、降低了时间复杂度、避免了暴力的搜索。

往往类似于“请找到满足xx条件的最x区间/子串/子数组”这一类问题都可以使用滑动窗口法来进行解决。

[LeetCode滑动窗口问题专区][LeetCode]

# 涉及题目 #

## 中等难度 ##

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

**题目地址**  
[3. 无重复字符的最长子串][3.]

**题目描述**  
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

> 输入: s = “”  
> 输出: 0

提示：

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

**题目思路**  
对于这道题，需要找到最长的连续、不重复字符的子串。

经过之前的经验，我们可以得知，可以使用滑动窗口的方法来找到这样的满足条件的连续字符串。

这里，条件是**对应的子串中不能有重复的字符**。因此，这里我们需要定义一个hash\_map来保存最新的字符所对应的下标，并在right遍历字符串的过程中，定义left，表示左边界——即不存在重复字符的最左位置。

对于遍历到的字符，判断该字符是否在对应的字符字典中，以及如果在其中，判断其出现的位置是否在left的范围内：

*  如果该字符未曾出现过，或者出现的位置在left的左边，说明该字符是可以作为不含重复字符串的子串的，并计算最新的最长子串长度。
 *  否则，就需要更新left——注意这里需要跳过当前的字符，因此left = right + 1。
 *  每次，都需要更新字符出现的位置字典。

最终，在right遍历到最后一个字符后，就可以得到这样最长的结果了。

**题目解法**

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            letter_index_map = {
        }
            left, right = 0, 0
            res = 0
            while right < len(s):
                curr_letter_index = letter_index_map.get(s[right])
                if curr_letter_index is None or curr_letter_index < left:
                    res = max(res, right - left + 1)
                else:
                    left = curr_letter_index + 1
                letter_index_map[s[right]] = right
                right += 1
            return res

### LeetCode 209. 长度最小的子数组 ###

**题目地址**  
[209. 长度最小的子数组][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

**题目思路**  
对于这道题，首先需要注意的是，并不是说要求连续子序列的累加和等于target，而是要大于target。

如果使用暴力求解的办法，自然也是可以做到的。但是，从题目的需求中我们可以看出，整体要求是满足“滑动窗口”的情景的。

这里，整体的算法流程接口也类似，首先，外层有一个right指针，内层再做相关的数据判断和左侧边界的处理——由于这种处理是基于条件的，因此也是需要一个while循环来实现。

因此，在算法的实现上，我们还是按照外层遍历、内层条件判断的策略，遍历整个数组，获得最终的结果。

**题目解法**

class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            left, right = 0, 0
            total_sum, res = 0, float('inf')
            while right < len(nums):
                total_sum += nums[right]
                while total_sum >= target:
                    res = min(res,right-left+1)
                    total_sum -= nums[left]
                    left += 1
                right += 1
            return 0 if res == float('inf') else res

### LeetCode 1004. 最大连续1的个数 III ###

**题目地址**  
[1004. 最大连续1的个数 III][1004. _1_ III]

**题目描述**  
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。  
返回仅包含 1 的最长（连续）子数组的长度。

示例 1：

> 输入：A = \[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：

> 输入：A = \[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.  1 <= A.length <= 20000
2.  0 <= K <= A.length
3.  A\[i\] 为 0 或 1

**题目思路**  
对于这道题，就是一道较为经典的滑动窗口类问题。  
在这道题中，是最初的求最长连续1的长度的变形——中间有0，并且有替换的数量，进而求最长的1的长度。

这里，我们定义一个滑动窗口 **\[left, right\]** 后，需要保证的窗口内全部都是1，这样最大的长度就是right - left + 1了。

但是，由于有0，这样就需要right在向右滑动时，需要判断A\[right\]是否为0：

*  如果是1，好说，直接向右滑动即可；
 *  如果是0，则需要记录curr\_zero\_num +=1，表示这一位我们置为了1——当然， 不可真的直接修改为1，否则后续left就无法得知A\[left\]原先到底是0还是1了。

当curr\_zero\_num为K时，则说明所有的0置为1的机会、我们此时已经用完了，因此，下一步就需要left向右移动了：

*  如果A\[left\]为1，也好说，直接继续右滑即可；
 *  如果是0，则说明可用的机会多了一个——原先为0的，目前我们已经不考虑了；

通过left向右的滑动，知道curr\_zero\_num再次小于K即可。

最后，不断计算right - left + 1的最大值即可。

**题目解法**

class Solution:
        def longestOnes(self, A: List[int], K: int) -> int:
            res = 0
            n = len(A)
            left = 0
            right = 0
            curr_zero_num = 0
            while right < n:
                if A[right] == 0:
                    curr_zero_num += 1
                while curr_zero_num > K:
                    if A[left] == 0:
                        curr_zero_num -= 1
                    left += 1
                res = max(res, right - left + 1)
                right += 1
            return res

[LeetCode]: https://leetcode-cn.com/tag/sliding-window/problemset/
[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[209.]: https://leetcode-cn.com/problems/minimum-size-subarray-sum/
[1004. _1_ III]: https://leetcode-cn.com/problems/max-consecutive-ones-iii/