给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
这题也是力扣上的一道题,直观上来说可以用暴力枚举,从第一个数字开始往后迭代,那样的话复杂度应该是过高了,我这里没有写代码,而是直接用的双指针法。
所谓的双指针无而非就是定义两个指针指向两个节点,然后通过判断关系来移动他们。根据不同的题意双指针的设定也不一样,但是大概来说的话,一般设置双指针的位置要么是类似滑动窗口的,同一起点同一方向移动,要么就是一个起点一个终点,相向而行。
这题由于是求最小的连续子数组,那显然是两个指针同时先指向起点。
以数组为2,3,1,4,3为例子。设定left,right指向2。我们要求数组和大于等于7,那么显然第一个点是小于7的,不满足条件要求,那么就要将right指针右移,直到left 和 right 构成的数组满足条件,那么这样的话就是left为起点的数组是最短的。将其记录下来,然后left也向右移动一格,这时left指向3,与前面一样的进行判断即可,如果3为起点满足条件的数组长度比之前的更短,那么就取这个数组长度即可,一直遍历到结尾。
最后在处理一下特殊情况和边界即可。 特殊情况其实就是当有一个值比s更大,那么返回的肯定是1。
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n=nums.size();
if(n==0) return 0;
int left=0,right=0,ans=INT_MAX;
int sum=nums[0];
while(right<n){
if(sum>=s){
int len=right-left+1;
if(len<ans) ans=len;
sum-=nums[left];
left++;
}
else{
right++;
if(right<n)
sum+=nums[right];
}
if(left>right) return 1;
}
if(ans!=INT_MAX) return ans;
return 0;
}
};