LeetCode 209. 长度最小的子数组
📌 题目描述
题目级别：中等
给定一个含有 n 个 正整数 的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
- 示例 1:
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
💡 破题思路：滑动窗口 (Sliding Window)
这道题之所以能用滑动窗口，核心底气在于题目规定了数组里全是**“正整数”**。这意味着：
- 窗口向右扩展（包含更多元素），总和一定变大。
- 窗口向左收缩（吐出已有元素），总和一定变小。
这就像一条毛毛虫在数组上爬行。
算法步骤：
💻 C++ 代码实现 (原汁原味作者版)
class Solution {
public:
int minSubArrayLen(int target, std::vector<int>& nums) {
int n = nums.size();
// len 初始设为 -1，巧妙地代表“尚未找到任何合法子数组”的初始状态
int sum = 0, len = –1, l = 0;
// 1. 窗口扩张：右指针 r 负责探路吞并元素
for (int r = 0; r < n; r ++ )
{
sum += nums[r];
// 2. 窗口收缩：一旦总和达标，尝试移动左边界榨取更短的长度
while (sum >= target)
{
// 如果是第一次找到 (len == -1)，或者找到了更短的区间，则更新 len
if (len == –1 || r – l + 1 < len) len = r – l + 1;
// 左指针吐出元素，然后向右走一步
sum -= nums[l];
l ++ ;
}
}
// 3. 收尾：如果 len 还是 -1，说明全程没达到过 target，返回 0
return len == –1 ? 0 : len;
}
};
