LeetCode Problem
209. Minimum Size Subarray Sum
Link to LeetCode
Given an array of positive integers nums and a positive integer target,
return the minimal length of a subarray whose sum is greater than or equal to target.
If there is no such subarray, return 0 instead.
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Analysis
We can use 2 points to mark the left and right boundaries of the sliding window. When the sum is greater than the target, shift the left pointer; when the sum is less than the target, shift the right pointer.
public int minSubArrayLen(int s, int[] nums) {
if(nums==null || nums.length==1)
return 0;
int result = nums.length;
int start=0;
int sum=0;
int i=0;
boolean exists = false;
while(i<=nums.length){
if(sum>=s){
exists=true; //mark if there exists such a subarray
if(start==i-1){
return 1;
}
result = Math.min(result, i-start);
sum=sum-nums[start];
start++;
}else{
if(i==nums.length)
break;
sum = sum+nums[i];
i++;
}
}
if(exists)
return result;
else
return 0;
}
//Similarly, we can also write it in a more readable way.
public int minSubArrayLen(int s, int[] nums) {
if(nums==null||nums.length==0)
return 0;
int i=0;
int j=0;
int sum=0;
int minLen = Integer.MAX_VALUE;
while(j< nums.length){
if(sum< s){
sum += nums[j];
j++;
}else{
minLen = Math.min(minLen, j-i);
if(i==j-1)
return 1;
sum -=nums[i];
i++;
}
}
while(sum>=s){
minLen = Math.min(minLen, j-i);
sum -=nums[i++];
}
return minLen==Integer.MAX_VALUE? 0: minLen;
}