在计算机网络中，滑动窗口协议（Sliding Window Protocol）是传输层进行流控的一种措施，接收方通过通告发送方自己的窗口大小，从而控制发送方的发送速度，从而达到防止发送方发送速度过快而导致自己被淹没的目的。我们所要讲解的滑动窗口算法也是利用了同样的特性。
滑动窗口算法（Sliding Window）：在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。
- 滑动操作：窗口可按照一定方向进行移动。最常见的是向右侧移动。
- 缩放操作：对于不定长度的窗口，可以从左侧缩小窗口长度，也可以从右侧增大窗口长度。
滑动窗口利用了双指针中的快慢指针技巧，我们可以将滑动窗口看做是快慢指针两个指针中间的区间，也可以将滑动窗口看做是快慢指针的一种特殊形式。
滑动窗口算法一般用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。该算法可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。
按照窗口长度的固定情况，我们可以将滑动窗口题目分为以下两种：
- 固定长度窗口：窗口大小是固定的。
- 不定长度窗口：窗口大小是不固定的。
- 求解最大的满足条件的窗口。
- 求解最小的满足条件的窗口。
下面来分别讲解一下这两种类型题目。
假设窗口的固定大小为 window_size。
- 使用两个指针
left、right。初始时，left、right都指向序列的第一个元素，即：left = 0，right = 0，区间[left, right]被称为一个「窗口」。 - 当窗口未达到
window_size大小时，不断移动right，先将window_size个元素填入窗口中。 - 当窗口达到
window_size大小时，判断窗口内的连续元素是否满足题目限定的条件。- 如果满足，再根据要求更新最优解。
- 然后向右移动
left，从而缩小窗口长度，即left += 1，使得窗口大小始终保持为window_size。
- 向右移动
right，将元素填入窗口中。 - 重复 2 ~ 4 步，直到
right到达序列末尾。
left = 0
right = 0
while right < len(nums):
window.append(nums[right])
# 超过窗口大小时，缩小窗口，维护窗口中始终为 window_size 的长度
if right - left + 1 >= window_size:
# ... 维护答案
window.popleft()
left += 1
# 向右侧增大窗口
right += 1下面我们根据具体例子来讲解一下如何使用固定窗口大小的滑动窗口来解决问题。
描述：给定一个整数数组 arr 和两个整数 k 和 threshold 。
要求：返回长度为 k 且平均值大于等于 threshold 的子数组数目。
说明：
-
$1 \le arr.length \le 10^5$ 。 -
$1 \le arr[i] \le 10^4$ 。 -
$1 \le k \le arr.length$ 。 -
$0 \le threshold \le 10^4$ 。
示例：
输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。
输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。这道题目是典型的固定窗口大小的滑动窗口题目。窗口大小为 k。具体做法如下：
ans用来维护答案数目。window_sum用来维护窗口中元素的和。left、right都指向序列的第一个元素，即：left = 0，right = 0。- 向右移动
right，先将k个元素填入窗口中。 - 当窗口元素个数为
k时，即：right - left + 1 >= k时，判断窗口内的元素和平均值是否大于等于阈值threshold。- 如果满足，则答案数目 + 1。
- 然后向右移动
left，从而缩小窗口长度，即left += 1，使得窗口大小始终保持为k。
- 重复 3 ~ 4 步，直到
right到达数组末尾。 - 最后输出答案数目。
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
left = 0
right = 0
window_sum = 0
ans = 0
while right < len(arr):
window_sum += arr[right]
if right - left + 1 >= k:
if window_sum >= k * threshold:
ans += 1
window_sum -= arr[left]
left += 1
right += 1
return ans- 时间复杂度：$O(n)$。
- 空间复杂度：$O(n)$。
- 使用两个指针
left、right。初始时，left、right都指向序列的第一个元素。即：left = 0，right = 0，区间[left, right]被称为一个「窗口」。 - 将区间最右侧元素添加入窗口中，即
window.add(s[right])。 - 然后向右移动
right，从而增大窗口长度，即right += 1。直到窗口中的连续元素满足要求。 - 此时，停止增加窗口大小。转向不断将左侧元素移出窗口，即
window.popleft(s[left])。 - 然后向右移动
left，从而缩小窗口长度，即left += 1。直到窗口中的连续元素不再满足要求。 - 重复 2 ~ 5 步，直到
right到达序列末尾。
left = 0
right = 0
while right < len(nums):
window.append(nums[right])
while 窗口需要缩小:
# ... 可维护答案
window.popleft()
left += 1
# 向右侧增大窗口
right += 14.3 无重复字符的最长子串
描述：给定一个字符串 s。
要求：找出其中不含有重复字符的最长子串的长度。
说明：
-
$0 \le s.length \le 5 * 10^4$ 。 -
s由英文字母、数字、符号和空格组成。
示例：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。用滑动窗口 window 来记录不重复的字符个数，window 为哈希表类型。
- 设定两个指针：
left、right，分别指向滑动窗口的左右边界，保证窗口中没有重复字符。 - 一开始，
left、right都指向0。 - 向右移动
right，将最右侧字符s[right]加入当前窗口window中，记录该字符个数。 - 如果该窗口中该字符的个数多于 1 个，即
window[s[right]] > 1，则不断右移left，缩小滑动窗口长度，并更新窗口中对应字符的个数，直到window[s[right]] <= 1。 - 维护更新无重复字符的最长子串长度。然后继续右移
right，直到right >= len(nums)结束。 - 输出无重复字符的最长子串长度。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
right = 0
window = dict()
ans = 0
while right < len(s):
if s[right] not in window:
window[s[right]] = 1
else:
window[s[right]] += 1
while window[s[right]] > 1:
window[s[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
right += 1
return ans- 时间复杂度：$O(n)$。
-
空间复杂度：$O(| \sum |)$。其中
$\sum$ 表示字符集，$| \sum |$ 表示字符集的大小。
描述：给定一个只包含正整数的数组 nums 和一个正整数 target。
要求：找出数组中满足和大于等于 target 的长度最小的「连续子数组」，并返回其长度。如果不存在符合条件的子数组，返回 0。
说明：
-
$1 \le target \le 10^9$ 。 -
$1 \le nums.length \le 10^5$ 。 -
$1 \le nums[i] \le 10^5$ 。
示例：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
输入：target = 4, nums = [1,4,4]
输出：1最直接的做法是暴力枚举，时间复杂度为
用滑动窗口来记录连续子数组的和，设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口中的和刚好大于等于 target。
- 一开始，
left、right都指向0。 - 向右移动
right，将最右侧元素加入当前窗口和window_sum中。 - 如果
window_sum >= target，则不断右移left，缩小滑动窗口长度，并更新窗口和的最小值，直到window_sum < target。 - 然后继续右移
right，直到right >= len(nums)结束。 - 输出窗口和的最小值作为答案。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
size = len(nums)
ans = size + 1
left = 0
right = 0
window_sum = 0
while right < size:
window_sum += nums[right]
while window_sum >= target:
ans = min(ans, right - left + 1)
window_sum -= nums[left]
left += 1
right += 1
return ans if ans != size + 1 else 0- 时间复杂度：$O(n)$。
- 空间复杂度：$O(1)$。
描述：给定一个正整数数组 nums和整数 k 。
要求：找出该数组内乘积小于 k 的连续的子数组的个数。
说明：
-
$1 \le nums.length \le 3 * 10^4$ 。 -
$1 \le nums[i] \le 1000$ 。 -
$0 \le k \le 10^6$ 。
示例：
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
输入：nums = [1,2,3], k = 0
输出：0- 设定两个指针：
left、right，分别指向滑动窗口的左右边界，保证窗口内所有数的乘积window_product都小于k。使用window_product记录窗口中的乘积值，使用count记录符合要求的子数组个数。 - 一开始，
left、right都指向0。 - 向右移动
right，将最右侧元素加入当前子数组乘积window_product中。 - 如果
window_product >= k，则不断右移left，缩小滑动窗口长度，并更新当前乘积值window_product直到window_product < k。 - 记录累积答案个数加
1，继续右移right，直到right >= len(nums)结束。 - 输出累积答案个数。
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
size = len(nums)
left = 0
right = 0
window_product = 1
count = 0
while right < size:
window_product *= nums[right]
while window_product >= k:
window_product /= nums[left]
left += 1
count += (right - left + 1)
right += 1
return count- 时间复杂度：$O(n)$。
- 空间复杂度：$O(1)$。