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

09. 长度最小的子数组

题目链接： 209. 长度最小的子数组 - LeetCode

题目描述： 给定一个含有 n 个正整数的数组和一个正整数 target。 找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例： 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

暴力解法（会超时）

思路很直接：枚举所有可能的起始位置，然后向后延伸直到和满足条件。记录所有满足条件的区间长度，取最小值。

这种方法的时间复杂度是 O(N²)，在数据量较大时必然超时，不推荐直接使用。

滑动窗口优化

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

核心逻辑： 维护一个窗口 [left, right]，动态调整左右边界来寻找满足条件的最小区间。

1. 右指针扩张：不断将 right 指向的元素加入窗口，累加当前和 sum。
2. 左指针收缩：一旦 sum >= target，说明当前窗口满足条件。此时尝试移动 left 缩小窗口，同时更新最小长度 len。只要 sum >= target，就持续收缩，因为去掉左边元素后可能依然满足条件。
3. 循环结束：当 right 遍历完数组，返回记录的最小长度。

为什么滑动窗口效率更高？ 很多人只记住了代码，却忽略了背后的原理。这里的关键在于指针不回退。

在暴力解法中，每次更换起始位置都要重新计算后面的和，存在大量重复劳动。而滑动窗口中，left 和 right 都只向右移动，每个元素最多被访问两次（一次进窗口，一次出窗口）。因此时间复杂度降为 O(N)。

C++ 代码实现：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int 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;
    }
};