长度最小的子数组（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

思路

这道题是一个很经典的滑动窗口问题，设置两个指针一个left一个right，将它们都初始化为0。之后先让左边界不变，移动右边界到滑动窗口框出来的所有数的和更好大于等于目标值，此时计算出当前滑动窗口长度并和最小值比较，若小于则替换最小值，之后滑动窗口的左边界向前进一步，同时当前滑动窗口的值要剪掉刚刚的左边界（因为进了一步，删掉了前一步的左边界）。最后一定一定不要忘记，不能直接输出当前最小值m，如果没有满足要求的值，此时的最小值依然为我们最开始初始化的最大值INT_MAX，因此要判断一下最小值是否为初始化的值，是则输出0表示没有满足要求的子数组，不是则输出当前最小值。

代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0,right=0;int m=INT_MAX;int sum=0;int n=nums.size();if(n==0) return 0;while(right<n){sum=sum+nums[right];while(sum>=target){m=min(m,right-left+1);sum=sum-nums[left];left++;}right++;}if(m==INT_MAX) return 0;else return m;}
};

时间复杂度

• 时间复杂度：O(n)。n为数组长度。

• 空间复杂度：O(1)。只需常数空间存放若干变量。