Was ist die Sliding-Window-Technik?

Question

Accepted Answer

Die **sliding-window**-Technik behält einen zusammenhängenden Bereich (Fenster) über einem Array oder String bei und verschiebt ihn, anstatt von vorne zu rechnen, und löst viele Subarray-/Substring-Probleme in **O(n)**.

## Die Idee

Erweitern Sie das Fenster, indem Sie die rechte Kante verschieben; verkleinern Sie es, indem Sie die linke Kante verschieben, wenn eine Einschränkung verletzt wird. Verwenden Sie die vorherige Berechnung wieder, anstatt neu zu scannen.

## Beispiel: maximale Summe eines beliebigen Fensters der Größe 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)
```

## Komplexität

- **Zeit:** O(n) — jedes Element tritt einmal in das Fenster ein und tritt einmal aus.
- **Platz:** O(1) für feste Fenster, O(k) bei Verfolgung des Inhalts.

## Wann man es verwendet / Fallstricke

Verwenden Sie für "längste/kürzeste/max Subarray mit Eigenschaft X" Probleme. Für **variable** Fenster verschieben Sie den linken Zeiger, um die Einschränkung wiederherzustellen. Achten Sie auf Off-by-One-Fehler beim Hinzufügen/Entfernen von Grenzelementen.

## Warum es wichtig ist

Das Schiebefenster eliminiert redundante Arbeit und verwandelt O(n·k)-Neuberechnung in einen einzigen Durchgang.

Es ist das Standard-Muster für Substring- und Subarray-Probleme, die ständig in Interviews auftauchen.

Der Gedanke — das vorherige Ergebnis wiederverwenden, anstatt neu zu berechnen — verallgemeinert sich auf Streaming und Echtzeitdaten.