Ce este tehnica sliding-window?

Question

IT Interview Practice · Accepted Answer

Tehnica **sliding-window** menține un interval contigu (fereastră) pe un array sau string și îl glisează în loc să recalculeze de la zero, rezolvând multe probleme de subarray/substring în **O(n)**.

## Ideea

Extindeți fereastra mutând marginea dreaptă; micșorați-o mutând marginea stângă atunci când o constrângere este încălcată. Reutilizați calculul anterior în loc să rescannați.

## Exemplu: suma maximă a oricărei ferestre de dimensiune 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)
```

## Complexitate

- **Timp:** O(n) — fiecare element intră și iese din fereastră o dată.
- **Spațiu:** O(1) pentru ferestre fixe, O(k) la urmărirea conținutului.

## Când să utilizați / capcane

Folosiți pentru probleme de "subarray cel mai lung/cel mai scurt/maxim cu proprietatea X". Pentru ferestre **variabile**, avansați indicatorul stâng pentru a restabili constrângerea. Atenție la erorile off-by-one la adăugarea/ștergerea elementelor de limită.

## De ce este important

Sliding window elimină munca redundantă, transformând O(n·k) recalcularea într-o singură trecere.

Este modelul de referință pentru probleme de substring și subarray care apar constant în interviuri.

Intuiția — reutilizați rezultatul anterior în loc să recalculați — se generalizează la streaming și date în timp real.

Ideea

Exemplu: suma maximă a oricărei ferestre de dimensiune k

Complexitate

Când să utilizați / capcane

De ce este important

Întrebări conexe