[LeetCode 209] Minimum Size Subarray Sum
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.
Example:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
This is a simpler version of LeetCode 862 Shortest Subarray with Sum at Least K. Each element is > 0. Both the binary search and deque solution work. However, because we only have positive integers in the input, we can further simplify the solution by using sliding window + two pointers. For each nums[i], advance the left pointer until the window sum is < s, update the best answer during this process. Then advance the right pointer for the next candidate ending number. Each number appears in the window once and kicked out of the window at most once, the runtime is O(N).
class Solution { public int minSubArrayLen(int s, int[] nums) { int ans = nums.length + 1; int left = 0, right = 0, sum = 0; for(; right < nums.length; right++) { sum += nums[right]; while(left <= right && sum >= s) { ans = Math.min(ans, right - left + 1); sum -= nums[left]; left++; } } return ans <= nums.length ? ans : 0; } }
Related Problems