The Idea: Slide, Don't Restart

Say you need the largest sum of any 3 consecutive numbers. The obvious way: for every start index, add up the next 3 numbers. That's O(n·k) work, and most of it is repeated.

Look at two neighbouring windows:

nums:  [2, 1, 5, 1, 3, 2]     k = 3
        [2  1  5]              sum 8
           [1  5  1]           8 - 2 + 1 = 7
              [5  1  3]        7 - 1 + 3 = 9
                 [1  3  2]     9 - 5 + 2 = 6

They share k − 1 numbers. When the window slides one step, only two things change: one number enters on the right and one leaves on the left. So you update the sum in O(1) instead of re-adding k numbers. That's the whole trick, and it makes the scan O(n).

How to recognise a window problem. Look for all three of these:

1. The input is a sequence: an array or a string.
2. The question is about a contiguous piece of it: a subarray or a substring.
3. You want the longest / shortest / max / min / count of such pieces that satisfy some rule ("at most k distinct", "sum ≥ target", "no repeats").

Windows come in two flavours:

• Fixed size: "every window of length k". The window just slides. (This lesson.)
• Variable size: "the longest substring such that…". The window grows and shrinks. (Next lesson.)

The fixed-size template. Walk right over every index. Add nums[right]. Once the window is longer than k, remove nums[right - k]. Once it has exactly k items (right >= k - 1), record an answer. No special case for the first window.