Mikä on liukulikkunatekniikka?

Question

IT Interview Practice · Accepted Answer

**Sliding-window**-tekniikka ylläpitää vierekkäistä aluetta (ikkunaa) taulukon tai merkkijonon yli ja liukuu sitä sen sijaan, että laskettaisiin uudelleen alusta, ratkaisee monia alijoukko/osamerkkijono-ongelmia **O(n)**:ssä.

## Idea

Laajenna ikkunaa siirtämällä oikeaa reunaa; pienennä sitä siirtämällä vasenta reunaa, kun rajoitus rikkoutuu. Käytä uudelleen edellistä laskelmaa uudelleenskannauksen sijaan.

## Esimerkki: koko k:n minkä tahansa ikkunan maksimisumma

```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)
```

## Monimutkaisuus

- **Aika:** O(n) — jokainen elementti tulee ja poistuu ikkunasta kerran.
- **Tila:** O(1) kiinteille ikkunoille, O(k) sisällön seurannassa.

## Milloin käyttää / sudenkuopat

Käytä "pisin/lyhin/max alijoukko ominaisuudella X" -ongelmiin. **Muuttuville** ikkunoille siirrä vasenta osoitinta rajoituksen palauttamiseksi. Varo off-by-one-virheitä rajaelementin lisäyksessä/poistossa.

## Miksi se on tärkeää

Liukulikkuna eliminoi redundantin työn, muuttaen O(n·k) uudelleenlaskentaa yhteen läpikäyntiin.

Se on vakio-kuvio osamerkkijono- ja alijoukko-ongelmille, jotka esiintyvät jatkuvasti haastatteluissa.

Vaistuma — käytä edellistä tulosta uudelleen uudelleenlaskennan sijaan — yleistyy suoratoistoon ja reaaliaikaiseen dataan.

Idea

Esimerkki: koko k:n minkä tahansa ikkunan maksimisumma

Monimutkaisuus

Milloin käyttää / sudenkuopat

Miksi se on tärkeää

Aiheeseen liittyvät kysymykset