在计算机网络中，滑动窗口协议（Sliding Window Protocol）是传输层进行流控的一种措施，接收方通过通告发送方自己的窗口大小，从而控制发送方的发送速度，从而达到防止发送方发送速度过快而导致自己被淹没的目的。我们所要讲解的滑动窗口算法也是利用了同样的特性。

- 滑动操作：窗口可按照一定方向进行移动。最常见的是向右侧移动。

- 缩放操作：对于不定长度的窗口，可以从左侧增大窗口长度，也可以从右侧缩小窗口长度。

滑动窗口利用了双指针中的快慢指针技巧，我们可以将滑动窗口看做是快慢指针两个指针中间的区间，也可以可以将滑动窗口看做是快慢指针的一种特殊形式。

滑动窗口算法一般用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。该算法可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

滑动窗口主要处理连续区间问题，按类型主要有如下三种：

- 固定长度窗口：窗口大小是固定的。

- 不定长度窗口：窗口大小是不固定的。

- 求解最大的满足条件的窗口。

- 求解最小的满足条件的窗口。

下面来分别讲解一下这两种类型题目。

假设窗口的固定大小为 `window_size`。

1. 使用两个指针 `left`、`right`。初始时，`left` 、`right` 都指向序列的第一个元素，即：`left = 0`，`right = 0` ，区间 `[left, right]` 被称为一个「窗口」。

2. 当窗口达到 `window_size` 大小时，判断窗口内的连续元素是否满足题目限定的条件。

1. 如果满足，再根据要求更新最优解。

2. 然后向右移动 `left`，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 `window_size`。

3. 向右移动 `right`，先将 `window_size` 个元素填入窗口中。

4. 重复 2 ~ 3 步，直到 `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` 的子数组数目。

这道题目是典型的固定窗口大小的滑动窗口题目。窗口大小为 `k`。具体做法如下：

1. `ans` 用来维护答案数目。`window_sum` 用来维护窗口中元素的和。

2. `left` 、`right` 都指向序列的第一个元素，即：`left = 0`，`right = 0`。

3. 向右移动 `right`，先将 `window_size` 个元素填入窗口中。

4. 当窗口元素个数为 `k` 时，即：`right - left + 1 > k` 时，判断窗口内的元素和平均值是否大于等于阈值

1. 如果满足，则答案数目 + 1。

2. 然后向右移动 `left`，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 `k`。

5. 重复 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

1. 使用两个指针 `left`、`right`。初始时，`left`、`right` 都指向序列的第一个元素。即：`left = 0`，`right = 0`，区间 `[left, right]` 被称为一个「窗口」。

2. 将区间最右侧元素添加入窗口中，即 `window.add(s[right])`。

3. 然后向右移动 `right`，从而增大窗口长度，即 `right += 1`。直到窗口中的连续元素满足要求。

4. 此时，停止增加窗口大小。转向不断将左侧元素移出窗口，即 `window.popleft(s[left])`。

5. 然后向右移动 `left`，从而缩小窗口长度，即 `left += 1`。直到窗口中的连续元素不再满足要求。

6. 重复 2 ~ 5 步，直到 `right` 到达序列末尾。

left = 0

right = 0

while right < len(nums):

window.append(nums[right])

while 窗口需要缩小:

# ... 可维护答案

window.popleft()

left += 1

# 向右侧增大窗口

right += 1

给定一个字符串 `s`。

要求：找出其中不含有重复字符的 最长子串 的长度。

用滑动窗口 `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

给定一个只包含正整数的数组 `nums` 和一个正整数 `target`。

要求：找出数组中满足和大于等于 `target` 的长度最小的「连续子数组」，并返回其长度。如果不存在符合条件的子数组，返回 `0`。

最直接的做法是暴力枚举，时间复杂度为 $O(n^2)$。但是我们可以利用滑动窗口的方法，在时间复杂度为 $O(n)$ 的范围内解决问题。

用滑动窗口来记录连续子数组的和，设定两个指针：`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

给定一个正整数数组 `nums`和整数 `k` 。

要求：找出该数组内乘积小于 `k` 的连续的子数组的个数。

滑动窗口求解。

设定两个指针：`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

- 【答案】[TCP 协议的滑动窗口具体是怎样控制流量的？ - 知乎](https://www.zhihu.com/question/32255109/answer/68558623)

- 【博文】[滑动窗口算法基本原理与实践 - huansky - 博客园](https://www.cnblogs.com/huansky/p/13488234.html)

- 【博文】[滑动窗口（Sliding Window）- lucifer.ren](https://lucifer.ren/leetcode/thinkings/slide-window.html)