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

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

C++

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

时间复杂度

$O(N)$

空间复杂度

$O(1)$

C++

class Solution {
public:/**void print(vector<int>& nums){printf("\n");for(int i=0;i<nums.size();i++){printf(" %d ",nums[i]);}printf("\n");}**/void swap(vector<int>& nums,int i,int j){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;}void sortNums(vector<int>& nums,int s,int e){if( s>e ){return;}int i=s;int j=e;int k=nums[s];while( i!=j ){while( j>i && nums[j]>=k ){j--;}swap(nums,i,j);while( j>i && nums[i]<=k ){i++;}swap(nums,i,j);}sortNums(nums,s,i-1);sortNums(nums,i+1,e);}int minSubArrayLen(int target, vector<int>& nums) {print(nums);sortNums(nums,0,nums.size()-1);print(nums);int i=nums.size()-1;int count=0;while( i>-1  ){//printf("target:%d_i:%d_nums[i]:%d.count:%d.\n",target,i,nums[i],count);if( target==nums[i] ){count++;break;}else if( target>nums[i] ){int leaveNum=target-nums[i];if(0==i && leaveNum>nums[i]){count=0;break;}if(0==i && leaveNum<nums[i]){count=0;break;}if( (i-1)>=0 && leaveNum>=nums[i-1] ){target=target-nums[i];count++;i--;continue;}if( (i-1)>=0 && leaveNum<nums[i-1] ){count++;count++;break;}}else{//target<nums[i]count++;break;}}return count;}
};

Java

class Solution {public int minSubArrayLen(int target, int[] nums) {int result=Integer.MAX_VALUE;int i=0;int length=0;int sum=0;for( int j=0;j<nums.length;j++ ){sum=sum+nums[j];while( sum>=target ){length=j-i+1;sum=sum-nums[i++];result=Math.min(result,length);}}return result==Integer.MAX_VALUE?0:result;}
}

时间复杂度

$O(N)$

空间复杂度

$O(1)$

Python

python">class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:result=float('inf');i=0;length=0;sum=0;for j in range(0,len(nums)):sum=sum+nums[j];while sum>=target:length=j-i+1;sum=sum-nums[i];i=i+1;result=min(result,length);if result==float('inf'):return 0;else:return result;

时间复杂度

$O(N)$

空间复杂度

$O(1)$