/**
* Given an array of n positive integers and a positive integer s, find the
* minimal length of a contiguous 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.
*
* More practice:
* If you have figured out the O(n) solution, try coding another solution of
* which the time complexity is O(n log n).
*
*/
public class MinimumSizeSubarraySum209 {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0 || s == 0) return 0;
int slow = 0;
int sum = 0;
int min = Integer.MAX_VALUE;
for (int fast=0; fast= s && slow < nums.length) {
min = Math.min(min, fast-slow+1);
sum -= nums[slow];
slow++;
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
public int minSubArrayLen2(int s, int[] nums) {
if (nums == null || nums.length == 0) return 0;
int minLen = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
int right = 0;
while (right < nums.length) {
sum += nums[right++];
while (sum >= s) {
if (right - left < minLen) {
minLen = right - left;
}
sum -= nums[left++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
public int minSubArrayLen3(int s, int[] nums) {
if (nums == null || nums.length == 0) return 0;
int lo = 1;
int hi = nums.length;
int minLen = Integer.MAX_VALUE;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (isValid(nums, mid, s)) {
if (mid < minLen) minLen = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
private boolean isValid(int[] nums, int len, int s) {
int sum = 0;
for (int i=0; i= s) return true;
}
for (int i=len; i= s) return true;
}
return false;
}
}