#滑动窗口

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

#背景问题

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

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

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

这里大小为 3 的子数组（所有可能的窗口）有：

• [2 1 5]
• [2 5 1]
• [5 1 3]，求出的数字和为 9 ，最大
• [1 3 2]

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

#朴素解法（暴力求解）

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

参考代码如下：

#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. 窗口继续后移，不断更新最大值

参考代码如下：

#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)$，因为每个元素最多被访问两次。

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