Back to DSA
Minimum Size Subarray Sum
mediumAn array of positive integers and a positive threshold value are provided. Find the length of the shortest contiguous subarray whose elements sum to at least the threshold. If no such subarray exists, return zero.
Examples
Example 1:
Input:
threshold = 10, nums = [1,4,2,5,3,1]Output:
3Explanation: The subarray [4,2,5] has sum 11, meeting the threshold. No shorter subarray reaches 10.
Example 2:
Input:
threshold = 20, nums = [2,2,2,2]Output:
0Explanation: The total of all elements is only 8, which is below 20.
Hints
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}Time complexity
O(n)Space complexity
O(1)