209. 长度最小的子数组【 力扣(LeetCode) 】

一、题目描述

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

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

二、测试用例

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

三、解题思路

1. 基本思路：
     维护一个满足题目条件的子序列，然后不断前移并记录最小长度。
2. 具体思路：
   • 定义：变量 len 用于记录最小长度，初始化为 n+1 ；变量 sum 用处记录子序列和，初始化为 0 ；变量 i 和 j 用于标记子序列的首和尾，初始化都为 0 。
   • 维护子序列：每次吸收一个新的元素到尾部，计算子序列和。判断是否可以舍弃头部，如果可以舍弃，则一直舍弃到不能舍弃为止。记录下满足条件的子序列，然后取最小。
   • 返回结果 len 。【len = n+1，说明没有满足条件的子序列，则返回 0 。】

四、参考代码

时间复杂度：$\mathrm{O}(n)$
空间复杂度：$\mathrm{O}(1)$

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int len=n+1;int sum=0;for(int i=0,j=0;j<n;j++){sum+=nums[j];while(sum-nums[i]>=target){sum-=nums[i++];}if(sum>=target)len=min(len,j-i+1);}return len==n+1?0:len;}
};