Why it works
- All numbers are positive, so a longer window has a bigger sum. Once a window is good, every longer window with the same right end is good too, but none of them is shorter: the only ones worth checking come from shrinking.
- The length is recorded while shrinking, at each good window, and shrinking goes on until the sum drops below the target. So for every right the shortest good window ending there is measured.
- Dropping the number at left is safe: the window from left to right was good and is already measured, and a later window starting at the same left would end further right, so it could only be longer.
Complexity
Time O(n): right passes each number once and left passes each number at most once, so the inner loop runs at most n times in all. Memory O(1).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗