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
The problem is very similar to subarray with sum of kbut with a small difference, in this case we have to find an array of minimum size.
The problem can be solved by maintaining 2 pointers, very similar to minimum window substring. start,end
pointers will be used to manage the size of window with sum k. The algo is as follows:
start
index and sum elements along the path, continue adding up elements as long it is not greater than kend
index and decrease the value arr[end]
from sum.public class Solution {
int minSubArrayLen(int s, int[] nums) {
int n = nums.length();
int ans = INT_MAX;
int end = 0;
int sum = 0;
for (int start = 0; start < n; start++) {
sum += nums[i];
while (sum >= s) {
ans = min(ans, start + 1 - end);
sum -= nums[end++];
}
}
return (ans != INT_MAX) ? ans : 0;
}
}