Medium Minimum Size Subarray Sum
22%
Accepted
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 -1 instead.
Have you met this question in a real interview?
Yes
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.
Challenge
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
/**
* @param nums: an array of integers
* @param s: an integer
* @return: an integer representing the minimum size of subarray
*/
public int minimumSize(int[] nums, int s) {
// write your code here
int sum = 0, len = Integer.MAX_VALUE, start = 0, end = 0;
while(end < nums.length){
while(end < nums.length && sum < s){
sum += nums[end++];
}
while(sum >= s){
len = Math.min(len, end - start);
sum -= nums[start++];
}
}
return len == Integer.MAX_VALUE ? -1 : len;
}
}
No comments:
Post a Comment