1. 概述
当我们在处理数组中某些连续子区间的问题时，滑动窗口算法是一种非常高效的技术。它能够将原本需要双重循环解决的问题优化为单层循环，从而显著降低时间复杂度。
本文将详细讲解滑动窗口算法的两种主要形式：
- 固定窗口大小：适用于子区间长度固定的情况
- 灵活窗口大小：适用于子区间长度不固定、需满足某种条件的情况
我们将通过两个经典示例分别说明其原理和实现方式，并对比它们的适用场景。
2. 理论思想
滑动窗口的核心思想是：**将双重循环转化为单层循环，从而将时间复杂度从 O(n²) 优化到 O(n)**。
使用条件
滑动窗口适用于以下情况：
- 题目要求找出数组中满足某种条件的连续子区间的最大/最小值
- 所有子区间按起始位置排序后，其结束位置也单调不减（即如果 L₁ ≥ L₂，则 R₁ ≥ R₂）
实现方式
我们维护两个指针 L（左边界）和 R（右边界），表示当前窗口的范围：
- 向右移动
R时，将新元素加入当前窗口 - 向右移动
L时，将旧元素移出当前窗口
每次窗口移动后，我们都对当前窗口进行计算并更新最优解。
3. 固定窗口大小
3.1 问题描述
给定一个长度为 n 的整数数组 A 和一个整数 k，求所有长度为 k 的连续子数组中，最大和是多少。
例如：
输入: A = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4
输出: 37 （对应子数组 [4, 2, 10, 23]）
3.2 暴力解法
暴力解法思路如下：
int maxSum = 0;
for (int i = 0; i <= n - k; i++) {
int sum = 0;
for (int j = i; j < i + k; j++) {
sum += A[j];
}
maxSum = Math.max(maxSum, sum);
}
时间复杂度：O(n × k)
对于大数组来说效率较低。
3.3 滑动窗口优化解法
我们可以利用窗口滑动特性，每次移动窗口时只需进行一次加法和一次减法即可更新当前窗口的和。
int maxSum = 0, windowSum = 0;
// 初始化第一个窗口的和
for (int i = 0; i < k; i++) {
windowSum += A[i];
}
maxSum = windowSum;
// 滑动窗口
for (int i = k; i < n; i++) {
windowSum += A[i] - A[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
✅ 时间复杂度：O(n)
❌ 仅适用于窗口大小固定的问题
4. 灵活窗口大小（双指针法）
4.1 问题描述
给定一个表示每本书阅读时间的数组 A 和一个总时间限制 k，我们希望找出最长的连续子数组，其总阅读时间不超过 k。
例如：
输入: A = [3, 1, 2, 4, 5], k = 8
输出: 3 （对应子数组 [1, 2, 4]）
4.2 暴力解法
暴力做法是遍历每个起点，然后尽可能向右扩展窗口，直到总时间超过 k。
int maxLength = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += A[j];
if (sum <= k) {
maxLength = Math.max(maxLength, j - i + 1);
} else {
break;
}
}
}
❌ 时间复杂度：O(n²)
4.3 滑动窗口优化解法（双指针）
我们使用两个指针 left 和 right，维护一个窗口 [left, right)，确保窗口内元素总和不超过 k。
int left = 0, right = 0, sum = 0, maxLength = 0;
while (right < n) {
sum += A[right];
while (sum > k) {
sum -= A[left];
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
right++;
}
✅ 时间复杂度：O(n)
⚠️ 注意：此方法要求数组元素非负，否则无法保证 left 不会倒退
5. 两种方法对比
| 特性 | 固定窗口大小 | 灵活窗口大小 |
|---|---|---|
| 窗口长度 | 固定 | 可变 |
| 使用场景 | 所有窗口长度一致 | 找满足条件的最长/最短窗口 |
| 时间复杂度 | O(n) | O(n) |
| 代表问题 | 最大连续 k 个数的和 | 最长子数组总和不超过 k |
| 要求 | 区间单调性 | 区间单调性 + 非负元素 |
6. 总结
滑动窗口是一种非常实用的算法技巧，适用于很多子数组/子字符串问题。它能将暴力解法的 O(n²) 优化为 O(n)，大大提升效率。
✅ 适用条件：
- 所有窗口的起始点递增时，结束点也递增
- 可以通过移动指针来维护窗口状态
⚠️ 注意事项：
- 固定窗口大小的滑动窗口更简单，但只能用于窗口长度已知的问题
- 灵活窗口大小的滑动窗口（双指针）更通用，但要注意数组元素非负性要求
掌握滑动窗口的关键在于理解其“窗口滑动”的本质，以及如何在移动过程中维护窗口内的状态。熟练掌握后，很多看似复杂的题目都可以迎刃而解。