滑动窗口实战：最小和子数组与最长无重复子串

09. 长度最小的子数组

题目链接：

209. 长度最小的子数组 - 力扣（LeetCode）

题目描述：

题目示例：

暴力求解

思路很直接：枚举数组中的任意一个元素作为起始位置，然后向后寻找一段最短的区间，使得这段区间的和大于等于目标值 target。遍历完所有可能的起始位置后，取其中的最小值即可。

不过这种双重循环的做法在数据量大时很容易超时，我们来看看更优的方案。

滑动窗口优化

既然问题关注的是【一段连续的区间】，滑动窗口是天然的选择。

核心思路： 维护一个窗口 [left, right]，让窗口内的元素和小于 target。当窗口内元素之和第一次大于等于目标值时，记录当前长度，并尝试收缩左边界以寻找更短的有效区间。

具体做法：

1. 扩张右边界：将右端元素纳入窗口，累加当前和。
2. 收缩左边界：如果当前和 sum >= target，说明找到了一个满足条件的区间。此时更新结果长度，并将左端元素移出窗口（同时 sum 减去该值），继续判断是否仍满足条件。因为左边的元素可能很小，移出一个后剩下的部分依然可能满足要求。
3. 继续扩张：如果不满足条件，则移动右指针，引入下一个元素。

为什么滑动窗口能提升效率？ 很多初学者会疑惑：为什么指针不回退？

假设我们找到了从 left1 开始的最优区间，终点是 right1。既然已经确定了 left1 开头的最佳解，就没必要再保留它了。如果像暴力法那样重置指针重新计算，会浪费大量已知的信息。而滑动窗口的妙处在于，当我们把 left1 移出窗口时，right1 不需要回退，因为它已经是满足条件的最远点。新的起点 left2 对应的终点只会比 right1 更远或持平，不会更近。这样左右指针都只向右移动，总复杂度降为 O(N)。

C++ 代码实现：

class Solution {
public:
    int minSubArrayLen( target, vector<>& nums) {
         n = nums.(), sum = , len = INT_MAX;
         ( left = , right = ; right < n; right++) {
            sum += nums[right]; 
             (sum >= target) {
                len = (len, right - left + ); 
                sum -= nums[left++]; 
            }
        }
         len == INT_MAX ?  : len;
    }
};