681. The Shortest Stretch That Reaches the Target
Given n POSITIVE values and a target t, print the length of the shortest
contiguous stretch whose sum is at least t. Print 0 if no stretch reaches it.
Trying every start and every end is O(n^2). A window does it in O(n): widen
on the right until the sum reaches t, then shrink from the left for as long as
it still reaches t, recording the length each time.
The left edge never moves backwards, so although both edges are inside the same loop, each index is visited at most twice.
The positive requirement is not decoration. With a negative value present, the sum can fall as the window widens and rise as it shrinks, so neither edge can be advanced safely and the whole method collapses. Problem #286 is the version with negatives, and it uses prefix sums instead for exactly this reason.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ t ≤ 1000000000` - `1 ≤ value ≤ 10000`
Input
The first line contains two integers n and t.
The second line contains n space-separated positive integers.
Output
Print one integer: the length of the shortest contiguous stretch summing to at least t, or 0 if there is none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.