Das Sliding Window
Vergrößere und verkleinere ein Fenster über eine Folge, um 'bestes/längstes/kürzestes Teil-Array'-Fragen in einem Durchlauf statt durch erneutes Scannen zu beantworten.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
Whenever a problem asks for the best, longest, or shortest contiguous subarray or substring, the sliding window is almost certainly the pattern. It's two pointers' more dynamic cousin: instead of converging from the ends, a window grows and shrinks as it slides across the sequence, so you never re-scan the same elements.
Grow, then shrink
A window is a range [left, right]. You expand it by moving right forward, adding elements;
when the window violates a constraint, you shrink it by moving left forward, removing
elements. Each pointer only ever moves forward, so the whole scan is O(n) even though the window
resizes constantly.
The template for "longest window satisfying a condition":
// longest substring with at most K distinct characters — O(n)
int longestWithKDistinct(String s, int k) {
Map<Character, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
count.merge(c, 1, Integer::sum); // grow: add s[right]
while (count.size() > k) { // shrink while invalid
char l = s.charAt(left++);
if (count.merge(l, -1, Integer::sum) == 0) count.remove(l);
}
best = Math.max(best, right - left + 1); // window is valid here
}
return best;
}The magic is that left never moves backward. Even though the inner while looks like a nested
loop, across the whole run left advances at most n times total - so the algorithm is O(n), not
O(n²).
Why not just check every subarray?
The brute force generates every subarray (O(n²) of them) and checks each - O(n³) or O(n²). The window avoids that by observing that when you extend a valid window by one element and it becomes invalid, you don't restart - you just trim the left edge until it's valid again, reusing all the work in between.
Fixed vs. variable windows
Some problems use a fixed-size window (e.g. "max sum of any k consecutive elements") - slide a window of constant width k, adding the new element and removing the old one each step. Others use a variable-size window (like the K-distinct example) that grows and shrinks to satisfy a condition. Spotting which kind you need is half the battle.
Looking out a moving train, the window frames a stretch of landscape. As the train rolls forward, new scenery enters on one side and old scenery leaves on the other - you never re-view what already passed. A sliding window over an array is the same: the frame moves forward, admitting new elements at the right edge and dropping stale ones at the left, so each element is seen as it enters and leaves exactly once.
Given a string, find the length of the longest substring with no repeated character. Describe the window: what makes it invalid, how you shrink it, and why the whole thing is O(n) despite the inner shrink loop.
Why is a sliding window O(n) even though it has an inner shrink loop?
Key takeaways
- Sliding window solves 'best/longest/shortest contiguous subarray or substring' problems in O(n).
- Expand the window by moving right; shrink from the left when a constraint is violated.
- It's O(n) because both pointers only move forward - each element enters and leaves the window once.
- Fixed-size windows slide a constant width; variable-size windows grow and shrink to meet a condition.
- It beats the O(n^2)/O(n^3) 'check every subarray' brute force by reusing work instead of restarting.