题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

    解题方法

    滑动窗口

    由于所求子序列连续，故可以使用滑动窗口。
    子序列和小于目标值时向右扩增；反之记录子序列长度并删除左侧元素。
    最终返回最小子序列长度，若无则返回0；

c++代码：

  1. class Solution {
  2. public:
  3.     int minSubArrayLen(int target, vector<int>& nums) {
  4.         int n = nums.size();
  5.         int left=0, right=0;
  6.         int sum = 0;
  7.         int length = n+1;
  8.         int sublen = 0;
  10.         for(right=0; right<n; right++) {
  11.             sum = sum + nums[right];
  12.             while(sum>=target) {
  13.                 sublen = right - left + 1;
  14.                 length = sublen<length ? sublen:length;
  15.                 sum = sum - nums[left];
  16.                 left++;
  17.             }
  18.         }
  19.         return length==n+1 ? 0:length;
  20.     }
  21. };