Somas em Janelas de Tamanho Fixo

Muitas tarefas pedem a soma de cada bloco de k elementos consecutivos. Recalcular cada bloco do zero é desperdício, e você pode fazer melhor. 🪟

A ideia ingênua soma cada janela de comprimento k separadamente. Isso repete trabalho e custa O(n vezes k), o que é lento demais para entradas grandes.

Janelas vizinhas se sobrepõem quase completamente. Ao avançar uma posição para a direita, você apenas remove o elemento mais à esquerda e adiciona um novo elemento à direita.

Comece somando uma vez os primeiros k elementos. Essa única soma será a base que você continuará atualizando à medida que a janela avançar.

Para mover a janela, adicione o elemento que entra e subtraia aquele que sai. Assim, cada etapa realiza uma quantidade constante de trabalho, O(1).

Após cada deslocamento, atualize o que for necessário, como a máxima soma de janela encontrada até o momento. O valor da janela estará sempre disponível instantaneamente.

Você acessa cada elemento para adicioná-lo e mais uma vez para removê-lo, portanto a varredura completa é O(n). Isso atende facilmente a restrições grandes.

O elemento que sai da janela é a[i - k], não a[i - 1]. Acertar esse deslocamento é o erro mais comum em janelas fixas.

Precisa da maior média de janela em vez da soma? Basta dividir por k a soma de janela acompanhada. A lógica deslizante não muda em nada.

Se o vetor for menor que k, nenhuma janela completa existirá. Compare len(a) com k logo no início e retorne para evitar um erro de índice.

Use este padrão sempre que o comprimento da janela for fixo e você puder combinar valores com baixo custo, como em somas, contagens ou estatísticas simples acumuladas.

Você desliza uma janela de tamanho k uma posição para a direita ao longo de um vetor.

Inicialize a primeira janela uma vez, depois adicione e subtraia a cada etapa para deslizá-la em O(1). A varredura completa de tamanho fixo é executada em tempo linear. ✅