Hva er sliding-window-teknikken?

Question

Accepted Answer

**Sliding-window**-teknikken opprettholder et sammenhengende område (vindu) over en array eller string og glir det i stedet for å beregne på nytt, og løser mange subarray-/substring-problemer i **O(n)**.

## Ideen

Utvid vinduet ved å flytte høyre kant; krymp det ved å flytte venstre kant når en begrensning er brutt. Gjenbruk den forrige beregningen i stedet for å skanne på nytt.

## Eksempel: maksimal sum av ethvert vindu av 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 går inn og ut av vinduet én gang.
- **Plass:** O(1) for faste vinduer, O(k) når innhold spores.

## Når det skal brukes / fallgruver

Bruks for "lengste/korteste/maksimal subarray med egenskap X"-problemer. For **variable** vinduer, flytt venstre peker for å gjenopprette begrensningen. Vær oppmerksom på off-by-one-feil når grenselementene legges til/fjernes.

## Hvorfor det er viktig

Sliding window eliminerer redundant arbeid, og omgjør O(n·k)-omberegning til ett pass.

Det er standardmønsteret for substring- og subarray-problemer som dukker opp konstant i intervjuer.

Innsikten — gjenbruk det forrige resultatet i stedet for å beregne på nytt — generaliserer til streaming og sanntidsdata.