Why it works
- Next to each other, two windows share k - 1 numbers. So the new sum is the old one plus the number that came in minus the one that left: O(1) per step instead of adding k numbers again.
- All windows have the same length k, so the largest sum is the largest average. Comparing sums keeps the numbers whole, and the division happens once, at the end.
- best starts at -∞, not 0: if every number were negative, every sum would be below 0, and best = 0 would come out as a wrong answer.
Complexity
Time O(n): each number comes into the window once and leaves once. Memory O(1): only the sum, best and the index.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗