滑动窗口算法详解
滑动窗口是双指针算法的一种特殊形式。当两个指针从开始到结束始终朝同一方向移动，且不会反向时，就构成了滑动窗口。这种结构常用于解决连续子数组或子串的问题，能将时间复杂度从 O(N²) 优化至 O(N)。
1. 核心原理
在使用双指针时，若出现两个指针从开始到结束一直都是朝着同一个方向移动的，并且都不会出现超另一个方向移动的情况，这就叫做滑动窗口。之所以命名为'窗口'，是因为两个指针一直朝着同一个方向移动就像一个大小可能会变化的窗口一样。
理解了概念后，我们通过一道经典题目来验证其逻辑的正确性。
1.1 最小长度子数组
题目要求找到和大于等于 target 的最短连续子数组。注意必须是连续的区间。
暴力解法会遍历所有可能的起点和终点，时间复杂度为 O(N²)，在数据范围较大时会超时。优化的关键在于：当 right 移动到某位置使得区间和满足条件时，我们不需要将 left 回退，只需将 left 右移尝试缩小窗口即可。因为如果当前区间 [left, right] 满足条件，那么 [left+1, right] 的和一定更小，可能不再满足，但 right 无需回退。
为什么滑动窗口效率更高？
- 窗口寻找的是以当前最左侧元素为基准，满足条件的最右侧边界。
- 一旦找到最优区间，就可以大胆舍去左侧元素，避免重复计算。
- 利用前缀和的思想，剔除左侧元素只需减去对应值，无需重新累加。
代码实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// len 为满足条件的子数组的最小值，初始化为最大值
// sum 为 left 到 right 区间内的元素值之和
int n = nums.size(), len = INT_MAX, sum = 0;
for ( left = , right = ; right < n; right++) {
sum += nums[right];
(sum >= target) {
len = (right - left + , len);
sum -= nums[left++];
}
}
len == INT_MAX ? : len;
}
};
