---
title: "滑动窗口"
description: "前缀和、差分、双指针、滑动窗口等高频算法套路。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 滑动窗口

![](https://img.dailyup.xyz/originals/8208462639250-d9673793-dd96-466f-8a52-4eaf021537c3.png)


滑动窗口（Sliding Window）是一种用于处理**数组/字符串子区间问题**的高效算法。它通过维护一个动态的“窗口”，在遍历数据时调整窗口的起始和结束位置，从而避免重复计算，降低时间复杂度。

## 背景问题

给定一个长度为 `n` 的整数数组和一个固定窗口大小 `k`，我们需要找到所有长度为 `k` 的连续子数组，并计算它们的和，最终返回最大的那个和。

例如，对于下面的输入数据：

```
6 3
2 1 5 1 3 2
```

第一行包括两个整数，第一个 `n` 为 6，表示接下来要输入 6 个整数（第二行的整数），第一行中的第二个数字 `k` 为 3，表示要求大小为 3 的子数组的最大数字和。

这里大小为 3 的子数组（所有可能的窗口）有：
- `[2 1 5]`
- `[1 5 1]`
- `[5 1 3]`，求出的数字和为 9 ，最大
- `[1 3 2]`

这几个子数组中，数字和最大的为 9，由 `[5 1 3]` 这三个数字求和得到。

## 朴素解法（暴力求解）

同样的，我们可以用枚举的方法去实现，从左至右，依次选一个数字，然后接下来连续的三个数字之和，再选下一个数字，连续三个数字求和，在所有的数字和中选取最大值，即是结果。

参考代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, k, mx, q[110];

int main() {
  cin >> n >> k;
  
  for (int i = 0; i < n; i++) cin >> q[i];
  
  // 枚举去求最一个 k 子数组的数字和
  for (int i = 0; i < n - k + 1; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) {
      sum += q[j];
    }
    // 找子数组数字和的最大值
    if (sum > mx) mx = sum;
  }
  
  cout << mx << endl;
  
  return 0;
}
```

朴素解法的时间复杂度为 $O(n \times k)$。

## 滑动窗口法求解

我们可以利用滑动窗口技巧来优化，更高效的解决此类问题。

顾名思义，这里的连续 3 个元素的一组数就是一个“窗口”，这个“窗口”，是在不断变化的（向后滑动）。

滑动窗口又分为固定大小与可变大小两种类型的窗口，我们这里是固定大小窗口。

如果用滑动窗口来求解，关键步骤为：
1. 先计算第一个窗口的和
2. 后续窗口的和 = 前一个窗口的和 - 左边界离开的元素 + 右边界新进入的元素
3. 窗口继续后移，不断更新最大值

![](https://img.dailyup.xyz/originals/8208462640203-bcb21ac4-e863-4089-85d9-856fafb42abe.jpg)

参考代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, k, mx, q[110];

int main() {
  cin >> n >> k;
  
  for (int i = 0; i < n; i++) cin >> q[i];
  
  int window_sum = 0;
  for (int i = 0; i < k; i++) {
    window_sum += q[i];
  }
  
  int mx_sum = window_sum;
  
  // 滑动窗口
  for (int right = k; right < n; right++) {
    int left = right - k; // 左边界
    window_sum = window_sum - q[left] + q[right]; // 更新窗口数字和
    mx_sum = max(mx_sum, window_sum); // 更新最大值
  }
  
  cout << mx_sum << endl;
  
  return 0;
}
```

可以发现，使用滑动窗口技巧来解决这个问题，每个元素只被访问两次（进入窗口一次，离开窗口一次），时间复杂度降为 $O(n)$；
## 滑动窗口代码框架

【TODO： 补充】


## 滑动窗口的应用场景

滑动窗口适用于：

1. **连续子数组/子字符串**问题。
2. **求最大/最小满足条件的窗口**。
3. **数据是线性结构**（数组、字符串、链表）。

## 总结

使用滑动窗口可以将时间复杂度从暴力求解的 $O(n^2)$ 优化到 $O(n)$，因为每个元素最多被访问两次。

大家尽量多做相关的典型题目，在做的过程中再去理解框架，再尝试修改条件（如求最大值/最小值）。

Source: https://cppguide.xyz/algopatterns/slidingwindow/index.mdx