Vad är sliding-window-tekniken?

Question

Accepted Answer

**Sliding-window**-tekniken upprätthåller ett sammanhängande intervall (fönster) över en array eller sträng och glider det i stället för att omberäkna från början, vilket löser många subarray/substring-problem i **O(n)**.

## Idén

Utöka fönstret genom att flytta högerkanten; krympa det genom att flytta vänserkanten när en begränsning bryts. Återanvänd tidigare beräkning istället för att genomsöka igen.

## Exempel: maximal summa för något fönster av storlek 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)
```

## Komplexitet

- **Tid:** O(n) — varje element enters och leaves fönstret en gång.
- **Rum:** O(1) för fasta fönster, O(k) när innehållet spåras.

## När du använder / fallgropar

Använd för "längsta/kortaste/största subarray med egenskap X"-problem. För **varierande** fönster, flytta vänster pekare för att återställa begränsningen. Se upp för off-by-one-fel när du lägger till/tar bort gränselement.

## Varför det spelar roll

Sliding window eliminerar redundant arbete och förvandlar O(n·k) omberäkning till ett pass.

Det är standardmönstret för substring- och subarray-problem som dyker upp konstant i intervjuer.

Insikten — återanvänd tidigare resultat istället för att omberäkna — generaliserar till streaming och realtidsdata.