Minimum Size Subarray Sum

Problem

You are given an array of positive integers nums and a positive integer target. Find the length of the shortest contiguous subarray whose elements sum to at least target. If no subarray reaches the target, return 0.

• nums has between 1 and 100,000 elements, each a positive integer no larger than 10,000.
• target is a positive integer up to 10^9, so the sum of the entire array may fall short of it.

Examples

• nums = [4, 1, 6, 2, 8, 3], target = 11 → 2. [8, 3] reaches 11 in two elements; no single element does.
• nums = [2, 9, 5], target = 9 → 1. The 9 on its own meets the target.
• nums = [3, 3, 3, 3], target = 20 → 0. The whole array only sums to 12.

Hints

1. All numbers are positive. What happens to a subarray's sum as you extend it, and as you trim it?
2. Once a window's sum reaches the target, extending it further cannot make it shorter, so what should you do instead?
3. Sliding window: grow the right end until the sum is at least target, then shrink from the left while it still is, recording the length at each shrink step.