209. Minimum Size Subarray Sum #

Problem #

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 1:

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).

Problem Summary #

Given an integer array and a number s, find the shortest contiguous subarray in the array such that the sum of the numbers in the contiguous subarray sum>=s, and return the length of the shortest contiguous subarray.

Solution Approach #

The solution idea for this problem is to use a sliding window. Continuously move backward within the sliding window [i,j]. If the total sum is less than s, expand the right boundary j and continuously add the values on the right until sum > s, then shrink the left boundary i, continuously shrinking until sum < s. At this point, the right boundary can move to the right again. Repeat this process.

Code #

package leetcode

func minSubArrayLen(target int, nums []int) int {
	left, sum, res := 0, 0, len(nums)+1
	for right, v := range nums {
		sum += v
		for sum >= target {
			res = min(res, right-left+1)
			sum -= nums[left]
			left++
		}
	}
	if res == len(nums)+1 {
		return 0
	}
	return res
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}