长度最小的子数组
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 连续
子数组
[numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0
。
示例 1:
1 2 3
| 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
|
示例 2:
1 2
| 输入:target = 4, nums = [1,4,4] 输出:1
|
示例 3:
1 2
| 输入:target = 11, nums = [1,1,1,1,1,1,1,1] 输出:0
|
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
- 如果你已经实现
O(n)
时间复杂度的解法, 请尝试设计一个 O(n log(n))
时间复杂度的解法。
先想一个暴力解法:固定一个起点i
,j
从i
开始遍历,如果满足[i,j]
的总和大于等于target
则记录下区间的长度,返回区间长度的最小值。可以用前缀和来减少一些计算量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n=nums.size(); vector<int> s(n+1,0); int ans=n+1; for(int i=1;i<=n;i++) s[i]=s[i-1]+nums[i-1]; for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ if(s[j+1]-s[i]>=target){ ans=min(ans,j-i+1); break; } } } return ans>n?0:ans; } };
|
但是时间复杂度为平方级别,超时了。
注意到数组里均为正整数,所以前缀和数组是递增的,所以可以用二分搜索来优化暴力解法中寻找终点j
的过程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n=nums.size(); vector<int> s(n+1,0); int ans=n+1; for(int i=1;i<=n;i++) s[i]=s[i-1]+nums[i-1]; for(int i=0;i<n;i++){ int l=i,r=n-1; while(l<r){ int mid=l+r>>1; if(s[mid+1]-s[i]>=target) r=mid; else l=mid+1; } if(s[l+1]-s[i]>=target) ans=min(ans,l-i+1); } return ans>n?0:ans; } };
|
时间复杂度O(nlogn)
这个题也是经典的滑动窗口模板题。
滑动窗口的原理:维护两个指针left
,right
和区间和。right
指针从左向右移动,并将nums[right]
加入区间和,如果区间和大于等于target
,则,尝试右移left
指针,判断移动后是否满足条件。记录区间长度,返回最小值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n=nums.size(); int ans=n+1; int sum=0; for(int left=0,right=0;right<n;right++){ sum+=nums[right]; while(sum>=target){ ans=min(ans,right-left+1); sum-=nums[left]; left++; } } return ans>n?0:ans; } };
|