滑动窗口算法核心思路与经典例题解析

引言：

滑动窗口？用两个指针维护一个动态的'窗口'区间，通过移动指针来扩大或缩小窗口，在一次遍历中完成计算，时间复杂度通常为 O(n)。

典型应用：寻找最长无重复字符的子串、找到和为目标值的最短子数组、字符串的排列匹配

一般步骤（模板）：

1. 定义 left 和 right 指针同时指向数组首元素；
2. 当符合要求时，right++，模拟进窗口；
3. 不满足要求时，left++，模拟出窗口；
4. 并根据具体情况更新结果。

结束条件：当 right 越界。

具体我们通过下面的题目来深入认识它。

209. 长度最小的子数组

题目描述：

实现核心及思路：

由于数组元素均为正整数，所以当求和时满足单调性，套用上面的模板：

1. 定义 left 和 right 指针，同时指向首元素；
2. right 指针向右移动，进窗口，并求和 sum；当和大于或等于 target 时，更新结果；
3. left 指针向右移动，出窗口，同时让 sum 减去 nums[left]，直到 sum 小于 target。

***注意：***在出窗口时，如果满足 sum >= target，也要更新结果。

思路可视化：

代码实现：

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