简要介绍
滑动窗口算法在笔试面试以及算法竞赛中非常常见，主要用于处理数组和字符串问题，特别适合寻找满足某个条件的子数组或子字符串，或者用于连续子问题的计算。
顾名思义，'滑动窗口'就是维护一个区间，这个窗口的大小可以是固定的也可以是变化的。它会在数据结构上移动来扫描数据。基本套路通常包括四个步骤：
- 进窗口：右指针移动，将新元素加入当前窗口。
- 判断条件：根据题意分析当前窗口是否满足要求。
- 更新结果：如果满足条件，记录或更新最优解。
- 出窗口：左指针移动，移除旧元素，缩小窗口以尝试更优解。
相关例题
长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其总和大于等于 target 的长度最小的 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
题目分析
这是一个典型的滑动窗口题目。暴力解法需要遍历数组两次，时间复杂度为 $O(n^2)$。考虑到数据规模可能达到 $10^5$，暴力解会超时。虽然可以使用前缀和加二分查找优化到 $O(n \log n)$，但滑动窗口可以将复杂度进一步降低到 $O(n)$。
实现思路
我们需要维护一个滑动窗口，窗口内的值之和小于目标值时继续扩张，一旦大于等于目标值就收缩左边界以寻找最小长度。具体过程如下：
定义两个指针，分别指向窗口的开头和结尾，同时初始化一个变量记录最大长度。接着开始维护窗口：首先将右指针当前指向的值加入窗口；然后判断窗口和是否大于等于目标值，如果是则更新结果并将左指针指向的值移出窗口（实现向右滑动）；最后右指针右移一位。
实现代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, len = INT_MAX;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right];
(sum >= target) {
len = (len, right - left + );
sum -= nums[left++];
}
}
len == INT_MAX ? : len;
}
};