Wat is de sliding-window-techniek?

Question

Accepted Answer

De **sliding-window**-techniek handhaaft een aaneengesloten bereik (venster) over een array of string en schuift dit in plaats van opnieuw te berekenen, waardoor veel subarray-/substring-problemen in **O(n)** worden opgelost.

## Het idee

Breid het venster uit door de rechterrand te verplaatsen; krimpit in door de linkerrand te verplaatsen wanneer een beperking wordt geschonden. Hergebruik de vorige berekening in plaats van opnieuw te scannen.

## Voorbeeld: maximale som van venster ter grootte k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Complexiteit

- **Tijd:** O(n) — elk element betreedt en verlaat het venster eenmaal.
- **Ruimte:** O(1) voor vaste vensters, O(k) bij het volgen van inhoud.

## Wanneer te gebruiken / valkuilen

Gebruikt voor "langste/kortste/maximale subarray met eigenschap X"-problemen. Voor **variabele** vensters, verplaats de linkerwijzer om de beperking te herstellen. Pas op voor off-by-one-fouten bij het toevoegen/verwijderen van grenselementjes.

## Waarom het belangrijk is

Sliding window elimineert overbodig werk en zet O(n·k)-herberekening om in één passage.

Het is het standaardpatroon voor substring- en subarray-problemen die voortdurend in interviews voorkomen.

Het inzicht — hergebruik het vorige resultaat in plaats van opnieuw te berekenen — generaliseert naar streaming en real-time gegevens.