Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array

the subarray

`[2,3,1,2,4,3]`

and `s = 7`

,the subarray

`[4,3]`

has the minimal length under the problem constraint.**Understand the problem:**

Since the array elements are all positive numbers, we could use a sliding window approach. W first move the front pointer until the sum of the subarray is greater or equal to the target value s, then we calculate the size of the window. Then we try to move the rear pointer and recalculate the window size, until the sum of the window is less than the target s.

**Code (Java):**

public class Solution { public int minSubArrayLen(int s, int[] nums) { if (s <= 0 || nums == null || nums.length == 0) { return 0; } int lo = 0; int hi = 0; int sum = 0; int minLen = Integer.MAX_VALUE; while (hi < nums.length) { // Moves the hi pointer while (hi < nums.length && sum < s) { sum += nums[hi]; hi++; } // Move the lo pointer while (lo <= hi && sum >= s) { minLen = Math.min(minLen, hi - lo); sum -= nums[lo]; lo++; } } if (minLen == Integer.MAX_VALUE) { return 0; } else { return minLen; } } }

## No comments:

## Post a Comment