Sliding window · 1 of 2
Sliding window technique
Keep a running summary of a subarray while its ends move forward, for windows of fixed length and windows that grow and shrink.
Books1
Links3
- Two Pointers Its Sliding Window section solves Books, the longest run of books that can be read within a time budget, by advancing the right end as far as the budget allows for each left end. usaco.guide (opens in a new tab)
- 双指针 (Two pointers) Maintains a range with two pointers. Its first example counts the subarrays whose product stays below a bound. oi-wiki.org (opens in a new tab)
- Open Data Structures, Chapter 1: Introduction Section 1.5 sets worst-case, amortized and expected running times side by side, with a house purchase that shows how a worst-case cost and an amortized cost differ. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code. opendatastructures.org (opens in a new tab)