Hvad er sliding-window-teknikken?

Question

Accepted Answer

**Sliding-window**-teknikken opretholder et sammenhængende område (vindue) over et array eller en streng og glider det i stedet for at genberegne fra bunden, løser mange subarray/substring-problemer i **O(n)**.

## Ideen

Udvid vinduet ved at flytte den højre kant; krympe det ved at flytte den venstre kant, når en begrænsning krænkes. Genbruge den tidligere beregning i stedet for at opscan.

## Eksempel: maksimal sum af ethvert vindue af størrelse 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)
```

## Kompleksitet

- **Tid:** O(n) — hvert element kommer ind i og ud af vinduet én gang.
- **Plads:** O(1) for faste vinduer, O(k) når indholdet spores.

## Hvornår skal man bruge / faldgruber

Brug til "længste/korteste/max subarray med egenskab X" problemer. For **variable** vinduer, avancer den venstre pointer for at gendanne begrænsningen. Pas på off-by-one fejl ved tilføjelse/fjernelse af grænseelementers.

## Hvorfor det betyder noget

Slidende vindue eliminerer unødigt arbejde, der transformerer O(n·k) genberegning til ét pass.

Det er go-to mønstret for substring og subarray problemer, der vises konstant i interviews.

Indsigten — genbruge det tidligere resultat i stedet for at genberegne — generaliserer til streaming og realtidsdata.