Sliding windows

A sliding window is a subarray you maintain as you walk forward. The fixed-size version is the one to learn first: the maximum sum of any k consecutive elements, for example.

Re-summing each block from scratch repeats almost the same additions. Once you know the sum of a window, the next window is the old sum, minus the element that left, plus the element that entered. That update is O(1), and you do it once per element, so the scan is O(n). The first window is the only one you build from nothing.

There is a second kind, the variable window, used when the size is part of the answer, such as the shortest subarray whose sum is at least a target. One pointer grows the window and the other shrinks it. Same idea, more bookkeeping. If k is larger than the array, there is no valid fixed window.