AI summary
type
status
date
slug
summary
category
tags
icon
password
滑动窗口的应用非常广泛，但我们的框架可以套用所有需要滑动窗口算法的题目中，下面就来举例一些最经典的题目，我会反复强调 滑动窗口算法核心代码模板 中的思考方式，以强化你对这个算法的理解和记忆。
📌
首先，看看如何把题目转化成子数组问题，从而使用滑动窗口来解决。

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

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
提示：
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4
  • 1 <= x <= 10^9
很多读者第一眼看到这个题，可能就想到了递归算法来穷举所有可能的操作方法对吧？每次我可以选择移除最左边或最右边的元素，然后对剩下的数组递归调用，直到 x 减到 0，肯定可以算出最小的操作数。
但是这道题的数据规模是 1 <= nums.length <= 10^5，这就意味着递归算法的时间复杂度不能达到 O(2^n) 这个级别，因为 10^5 的平方就是 10^10，这个数量级，在任何判题平台都是不能被接受的。
有了上面的分析，你必须再观察观察，转换一下思路。题目让你从边缘删除掉和为 x 的元素，那剩下来的是什么？剩下来的是不是就是 nums 中的一个子数组？让你尽可能少地从边缘删除元素说明什么？是不是就是说剩下来的这个子数组大小尽可能的大？
所以，这道题等价于让你寻找 nums 中元素和为 sum(nums) - x 的最长子数组。
寻找子数组就是考察滑动窗口技巧。前文说过，使用滑动窗口算法需要搞清楚以下几个问题：
  1. 什么时候应该扩大窗口？
  1. 什么时候应该缩小窗口？
  1. 什么时候得到一个合法的答案？
针对本题，以上三个问题的答案是：
  1. 当窗口内元素之和小于目标和 target 时，扩大窗口，让窗口内元素和增加。
  1. 当窗口内元素之和大于目标和 target 时，缩小窗口，让窗口内元素和减小。
  1. 当窗口内元素之和等于目标和 target 时，找到一个符合条件的子数组，我们想找的是最长的子数组长度。
注意：类似 713. 乘积小于 K 的子数组，之所以本题可以用滑动窗口，关键是题目说了 nums 中的元素都是正数，这就保证了只要有元素加入窗口，和一定变大，只要有元素离开窗口，和一定变小。
你想想如果存在负数的话就没有这个性质了，也就不能确定什么时候扩大和缩小窗口，也就不能使用滑动窗口算法，而应该使用 前缀和 + 哈希表的方式 解决，参见 560. 和为K的子数组。
养成特判的好习惯 if target < 0:，能减少样例的平均运行时间，即使不会也能过几个样例得点分，也许还能避免一些特殊情况下的 bug。
📌
上道题把题目变形成滑动窗口计算子数组和的问题，下面这道题来计算子数组的乘积。

713. 乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
提示:
  • 1 <= nums.length <= 3 * 10^4
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 10^6
典型的滑动窗口，直接套模版即可。
📌
在可以修改字符的条件下寻找符合条件的子数组，也可以用滑动窗口算法，以下是几道例题。

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
  1. 当可替换次数大于等于 0 时，扩大窗口，让进入窗口的 0 都变成 1，使得连续的 1 的长度尽可能大。
  1. 当可替换次数小于 0 时，缩小窗口，空余出可替换次数，以便继续扩大窗口。
  1. 只要可替换次数大于等于 0，窗口中的元素都会被替换成 1，也就是连续为 1 的子数组，我们想求的就是最大窗口长度。
有了这个思路，直接看代码吧。

340. 至多包含 K 个不同字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 至多 包含 k 个 不同 字符的最长子串，并返回该子串的长度。
秒了。

424. 替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度。
这题可以认为是上一道题 1004. 最大连续1的个数 III 的进阶版，上一题是确定 0 变 1，这题不确定要变成什么。
我们可以记录窗口中出现次数最多的字符（假设为字符 x，出现次数为 windowMaxCount），所以把所有字符都替换成 x 所需的替换次数就是 right - left - windowMaxCount。
当 right - left - windowMaxCount <= k 时，在可控范围内，整个窗口内的字符都可以替换成相同的；反之 right - left - windowMaxCount > k 时说明 k 次替换机会不足以使窗口内的字符全部相同，此时必须缩小窗口。
这里 window 也可以像上一题那样设为哈希表。
📌
在指定大小的子数组中寻找符合条件的元素，也可以用到滑动窗口算法，以下是几道例题。

219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
控制窗口大小为 k，往右滑，用集合存储元素，发现重复就返回 True
Tips：固定窗口大小的题目，第二个 while 可以换成 if，理由在上篇文章已经讲过了。

220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
找出满足下述条件的下标对 (i, j)：
  • i != j
  • abs(i - j) <= indexDiff
  • abs(nums[i] - nums[j]) <= valueDiff
如果存在，返回 true ；否则，返回 false 。
如何在窗口 [left, right) 中快速判断是否有元素之差小于 t 的两个元素呢？这就需要使用到 TreeSet 利用二叉搜索树结构寻找「地板元素」和「天花板元素」的特性了。
在 Python 中，对应的数据结构为 SortedList ，是 sortedcontainers 库提供的一种 自动保持有序 的列表数据结构。包括二分查找方法，找到距离 x 最近的位置：
  • bisect_left(x)：返回 x 应该插入的位置（左侧）
  • bisect_right(x)：返回 x 应该插入的位置（右侧）

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组  ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
秒了。
📌
最后，如果你不能直接回答滑动窗口算法的灵魂三问，理论上不能再使用滑动窗口算法了，但有时候可以尝试自己添加一些约束，从而能够使用滑动窗口算法来解决，下面是一道例题。

395. 至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
如果不存在这样的子字符串，则返回 0。
在本题的场景中，我们想尽可能多地装字符，即扩大窗口，但不知道什么时候应该开始收缩窗口。
为什么呢？比如窗口中有些字符出现次数不满足 k，但有可能再扩大扩大窗口就能满足 k 了呀？但要这么说的话，你干脆一直扩大窗口算了，所以你说不准啥时候应该收缩窗口。
理论上讲，这种情况就不能用滑动窗口模板了，但有时候我们可以自己添加一些约束，来进行窗口的收缩。
题目说让我们求每个字符都出现至少 k 次的子串，我们可以再添加一个约束条件：求每个字符都出现至少 k 次，仅包含 count 种不同字符的最长子串。
添加了字符种类的限制，我们就可以回答滑动窗口算法的三个灵魂问题了：
  1. 什么时候应该扩大窗口？窗口中字符种类小于 count 时扩大窗口。
  1. 什么时候应该缩小窗口？窗口中字符种类大于 count 时扩大窗口。
  1. 什么时候得到一个合法的答案？窗口中所有字符出现的次数都大于等于 k 时，得到一个合法的子串。
当然，题目没有 count 的约束，那没关系呀，count 能有几种取值？因为 s 中只包含小写字母，所以 count 的取值也就是 1~26，所以最后用一个 for 循环把这些值都输入 logestKLetterSubstr 计算一遍，求最大值就是题目想要的答案了。这充分体现了算法的本质是穷举。
滑动窗口算法的时间复杂度是 O(N)，循环 26 次依然是 O(26N) = O(N)。