Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array
[2,3,1,2,4,3] and s = 7,the subarray
[4,3] has the minimal length under the problem constraint.A:
two pointer
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if(nums == null || nums.length==0)
return 0;
int p1 =0,p2= -1; // both are inclusive
int minLen = Integer.MAX_VALUE;
long sum = 0;
while(p2<nums.length){
if(sum < s){
p2++;
if(p2<nums.length)
sum += nums[p2];
}else{
minLen = Math.min(minLen, p2-p1+1);
sum -= nums[p1++]; // do not need to check if p1<=p2, coz they s is positive
}
}
return minLen==Integer.MAX_VALUE?0:minLen;
}
}
Mistakes:
这道题的2大错误在于。
1： 刚开始用了 以前的双层循环的解法。 虽然复杂的没有变，但是写起来复杂了。 不好
2： 核心错误： 一开始p2没有确定是inclusive的，因此，开始没有设p2= -1;
***********第二遍*********
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int res = Integer.MAX_VALUE, pre = -1, sum = 0;
for(int i =0;i<nums.length;i++){
sum+= nums[i];
if(sum<s)
continue;
while( sum-nums[pre+1] >= s){
pre++;
sum -= nums[pre];
}
res = Math.min(i-pre,res);
sum = sum - nums[++pre];
}
return res == Integer.MAX_VALUE? 0 : res;
}
}
