leetcode 链接：209. 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例：

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

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

解答 & 代码

滑动窗口（窗口的左边界下标为 left，右边界下标为 right）

1. 如果窗口内的子数组和小于 target，则右边界逐步右移，直到窗口内子数组和大于等于 target，或右边界超出数组范围
2. 如果右边界超出数组范围，则停止滑动窗口（因为左边界再右移，窗口内子数组的和只会更小）
3. 否则，此时，窗口内子数组和大于等于 target，如果窗口长度小于之前符合要求的最小子数组长度 minSubLen，则更新 minSubLen。左边界右移一步，跳转回第 1 步循环

• 时间复杂度：O(n)，其中 n 是数组的长度。因为左右边界 left 和 right 最多各移动 n 次。

• 空间复杂度：O(1)。

  class Solution {
  public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        if(size == 0 || target <= 0)
            return 0;
  
        int minSubLen = size + 1;    // 符合要求的最小子数组长度
        int left = 0, right = 0;    // 滑动窗口的左、右边界下标
        int subSum = nums[0];        // 当前窗口内的元素和
        // 滑动窗口
        while(left < size)
        {
            while(subSum < target)    // 若窗口内元素和小于 target
            {
                ++right;            // 右边界右移
                if(right >= size)    // 若右边界越界，则退出循环
                    break;
                subSum += nums[right];    // 更新窗口内元素和
            }
            if(right >= size)        // 如果右边界越界，退出循环
                break;
            if(right - left + 1 < minSubLen)    // 更新最小数组长度
                minSubLen = right - left + 1;
            subSum -= nums[left];    // 更新窗口内元素和（去掉左边界元素）
            ++left;                    // 左边界右移
        }
  
        return minSubLen == size + 1 ? 0 : minSubLen;
    }
  };
  

  执行结果： ``` 执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 97.02% 的用户 内存消耗：10.4 MB, 在所有 C++ 提交中击败了 15.39% 的用户 ```