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
the subarray
Answer:[2,3,1,2,4,3]
and s = 7
,the subarray
[4,3]
has the minimal length under the problem constraint.traverse the array one time, Optimal method, using O(n)!
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int start=0,end=0;
int n=nums.length;
if(n==0){
return 0;
}
int currsum=nums[0];
int minLen=n+1;
boolean flag = false;
while(start<=end && end<n){
//if not satisfy the constraint, keep end index ++ and adding shift elements until satisfy.
while(currsum < s){
if(end<n-1){
currsum += nums[++end];
}else{// end index arrived to n-1.
if(flag == true){ //have found one.
return minLen;
}else{
return 0;
}
}
}
//if satisfy the constraint, keep start index ++ and substracting shift elements until not satisfy again.
while(currsum >= s){
int len = end-start+1;
if(len < minLen){
minLen = len;
flag = true;
}
if(start<=end){
currsum -= nums[start++];
}
}
}
return minLen;
}
}
No comments:
Post a Comment