题目描述：
给定一个含有 n 个正整数的数组和一个正整数 target。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。
算法原理：
解法一：暴力枚举出所有子数组的和；
解法二：利用单调性，使用“同向双指针”来优化，即使用滑动窗口来解决问题。
- 利用同向双指针、单调性：数组全是正数，窗口扩大 sum 变大，窗口缩小 sum 变小，right 不会回退，这是滑动窗口成立的核心；
- 流程顺序：
进窗口 → 判断（while 循环）→ 更新答案 → 出窗口，这个顺序完全和 AC 代码匹配； - 分支判断：
sum >= target：先记录当前窗口长度（更新最小长度），再收缩左边界（left++，sum 减去 nums[left]）sum < target：right 右移，把新元素加入窗口
- 理解了关键：满足条件之后，尝试收缩左边界找更小窗口，right 不用回头，这也是 O(n) 的根本原因。
- 当前窗口
[left, right]已经满足条件，对于固定 right，再往右扩 right 只会让窗口更长，不可能得到更短的答案，所以我们优先收缩 left 压榨最小长度；收缩完 left、sum 不满足条件之后，right 还要继续向右走，去探索后面新的窗口（比如样例里 right 走到 5 也就是元素 3 的时候，才找到答案 [4,3]）。 -
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0,right = 0; int n = nums.size(); int MINlen = INT_MAX; int sum =0; for(right = 0;right < n; right++) { sum+=nums[right];//进窗口 while(sum >= target) { MINlen = min(MINlen,right - left + 1);//更新结果 sum-=nums[left];//出窗口 left++; } } return MINlen == INT_MAX ? 0 : MINlen; } };
| 对比项 | 暴力枚举 | 滑动窗口 |
|---|---|---|
| 时间复杂度 | O(n²) | O(n) |
| 空间复杂度 | O(1) | O(1) |
| 是否利用单调性 | 否 | 是 |
| right 指针是否回退 | 是（每次重新枚举起点） | 否（只向右移动） |
滑动窗口之所以是 O(n)，是因为数组元素全为正数，窗口和随 right 右移单调递增、随 left 右移单调递减，left 和 right 各自最多移动 n 次，总操作次数为 2n，因此整体时间复杂度为 O(n)。
边界情况与总结
在实现滑动窗口时，除了主流程之外，还需要特别关注一些边界情况，避免出现越界、死循环或答案错误。
- target 大于数组总和：无论窗口怎么扩大，sum 都不可能达到 target，此时 while 循环一次都不会进入，MINlen 始终保持 INT_MAX，最终返回 0。代码中
return MINlen == INT_MAX ? 0 : MINlen;正是为此兜底，无需额外判断。 - 数组只有一个元素：right 从 0 开始，窗口只包含这一个元素。若
nums[0] >= target，while 进入一次，记录长度为 1，随后 left 右移使窗口为空，循环结束返回 1；若nums[0] < target，则返回 0。两种情况都符合题意，注意 left 右移后不要越界访问nums[left]。 - 存在多个最短子数组：题目只要求返回长度，不要求返回具体子数组，因此 while 循环中每次满足条件都更新
MINlen = min(MINlen, right - left + 1)即可，多个等长答案不会互相覆盖出错；若题目改为返回子数组本身，则需额外记录起止下标。 - target 恰好等于某个元素：窗口收缩到只剩该元素时 sum 仍满足条件，会记录长度 1，这是最小可能值，后续无需再优化。
最后用三条要点总结滑动窗口的核心思想与适用条件：
- 核心思想：用同向双指针维护一个连续区间
[left, right]，right 负责扩大窗口纳入新元素，left 负责在满足条件后收缩窗口压榨更优解，两个指针都只向右移动、绝不回退。 - 正确性来源：依赖单调性——数组元素全为正数时，窗口和随 right 右移单调递增、随 left 右移单调递减，因此一旦当前窗口满足条件，继续扩大 right 只会让窗口更长，可以放心收缩 left。
- 适用条件：问题求解的是连续子数组或子串，且窗口的某个指标（如和、计数）在扩大和收缩时具有单调性，同时需要满足「进窗口 → 判断 → 更新答案 → 出窗口」的固定流程，此时滑动窗口可将 O(n²) 的暴力枚举优化到 O(n)。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2603_95853495/article/details/170041060
