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.
click to show more practice.
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).
Credits:Special thanks to @Freezen for adding this problem and creating all test cases.
Hide Company Tags
Facebook
Hide Tags
Array Two Pointers Binary Search
Hide Similar Problems
(H) Minimum Window Substring (M) Maximum Size Subarray Sum Equals k
** 解題思路 **
Two pointers, O(n) Time complexity
/**
* @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) {
if (nums == null || nums.length == 0) return -1;
int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
while (j < nums.length) {
if (sum < s && j < nums.length) {
sum += nums[j++];
}
while (sum >=s ) {
min = Math.min(min, j - i);
sum -= nums[i++];
}
}
return min == Integer.MAX_VALUE ? -1 : min;
}
