O que é a técnica de sliding-window?

Question

IT Interview Practice · Accepted Answer

A técnica **sliding-window** mantém um intervalo contíguo (janela) em um array ou string e o desliza em vez de recalcular do zero, resolvendo muitos problemas de subarray/substring em **O(n)**.

## A ideia

Expanda a janela movendo a borda direita; encolha-a movendo a borda esquerda quando uma restrição é violada. Reutilize o cálculo anterior em vez de verificar novamente.

## Exemplo: soma máxima de qualquer janela de tamanho 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)
```

## Complexidade

- **Tempo:** O(n) — cada elemento entra e sai da janela uma vez.
- **Espaço:** O(1) para janelas fixas, O(k) ao rastrear conteúdo.

## Quando usar / armadilhas

Use para problemas de "subarray mais longo/mais curto/máximo com propriedade X". Para janelas **variáveis**, avance o ponteiro esquerdo para restaurar a restrição. Cuidado com erros off-by-one ao adicionar/remover elementos de limite.

## Por que isso importa

O sliding window elimina trabalho redundante, convertendo O(n·k) recálculo em uma única passagem.

É o padrão indicado para problemas de substring e subarray que aparecem constantemente em entrevistas.

O insight — reutilizar o resultado anterior em vez de recalcular — generaliza para streaming e dados em tempo real.

A ideia

Exemplo: soma máxima de qualquer janela de tamanho k

Complexidade

Quando usar / armadilhas

Por que isso importa

Perguntas relacionadas