Sliding Window — Uma Técnica para Trabalhar com Subarrays e Substrings

Sliding Window (janela deslizante) é uma técnica muito utilizada para resolver problemas que envolvem subarrays ou substrings consecutivas.

A ideia principal é manter uma "janela" sobre uma parte do array ou string e movimentá-la conforme processamos os dados.

Em vez de recalcular tudo do zero para cada possível intervalo, podemos aproveitar informações que já calculamos anteriormente.

Isso permite transformar muitos problemas que seriam:

O(n²)

ou até:

O(n³)

em soluções:

O(n)

A técnica aparece frequentemente em problemas de:

• Arrays
• Strings
• Subarrays
• Substrings
• Sequências consecutivas
• Soma de elementos
• Frequência de caracteres

1. O conceito de janela

Imagine o seguinte array:

[1, 2, 3, 4, 5]

Podemos criar uma janela de tamanho 3:

[1, 2, 3]  4  5
 ↑──────↑
  janela

Depois deslizamos a janela:

  1  [2, 3, 4]  5
      ↑──────↑
       janela

E novamente:

  1  2  [3, 4, 5]
          ↑──────↑
           janela

A janela está sempre representando uma parte consecutiva do array.

2. O problema clássico: Maximum Sum Subarray of Size K

Imagine que temos:

numbers = [2, 1, 5, 1, 3, 2]

k = 3

Queremos encontrar a maior soma de um subarray de tamanho 3.

As possibilidades são:

[2, 1, 5] = 8

[1, 5, 1] = 7

[5, 1, 3] = 9

[1, 3, 2] = 6

A maior soma é:

9

Portanto:

[5, 1, 3]

3. A solução de força bruta

Uma solução simples seria recalcular cada janela inteira.

function maxSum(numbers: number[], k: number): number {
  let max = -Infinity;

  for (let i = 0; i <= numbers.length - k; i++) {
    let sum = 0;

    for (let j = i; j < i + k; j++) {
      sum += numbers[j];
    }

    max = Math.max(max, sum);
  }

  return max;
}

O problema é que estamos recalculando os mesmos valores várias vezes.

Por exemplo:

[2, 1, 5]

Depois:

[1, 5, 1]

Os elementos:

1
5

aparecem nas duas janelas.

Mas a solução recalcula tudo novamente.

A complexidade é:

O(n × k)

Em muitos casos, isso pode chegar a:

O(n²)

4. A ideia do Sliding Window

Em vez de recalcular a soma inteira, podemos reutilizar o resultado anterior.

Primeira janela:

[2, 1, 5] 1 3 2

Soma:

2 + 1 + 5 = 8

Agora deslizamos:

2 [1, 5, 1] 3 2

O que mudou?

Saiu:

2

Entrou:

1

Então podemos calcular:

novaSoma = somaAtual - elementoQueSai + elementoQueEntra

Ou:

8 - 2 + 1 = 7

Não precisamos somar:

1 + 5 + 1

novamente.

5. Implementação

function maxSum(
  numbers: number[],
  k: number
): number {
  let windowSum = 0;
  let maxSum = -Infinity;

  for (let i = 0; i < numbers.length; i++) {
    windowSum += numbers[i];

    if (i >= k - 1) {
      maxSum = Math.max(
        maxSum,
        windowSum
      );

      windowSum -= numbers[i - k + 1];
    }
  }

  return maxSum;
}

Uso:

const result = maxSum(
  [2, 1, 5, 1, 3, 2],
  3
);

console.log(result);

Resultado:

9

Complexidade:

Time: O(n)

Space: O(1)

6. A visualização

Array:

[2, 1, 5, 1, 3, 2]

Primeira janela:

[2, 1, 5] 1 3 2

Soma:

8

Deslizando:

2 [1, 5, 1] 3 2

Calculamos:

8 - 2 + 1 = 7

Deslizando:

2 1 [5, 1, 3] 2

Calculamos:

7 - 1 + 3 = 9

Deslizando:

2 1 5 [1, 3, 2]

Calculamos:

9 - 5 + 2 = 6

Resultado:

max = 9

7. Janela de tamanho fixo

O exemplo anterior utiliza uma Fixed Sliding Window.

Ou seja:

k = 3

A janela sempre possui tamanho 3.

Visualmente:

[1, 2, 3] 4 5 6
 1 [2, 3, 4] 5 6
 1 2 [3, 4, 5] 6
 1 2 3 [4, 5, 6]

Esse tipo de janela é utilizado quando o problema diz algo como:

Encontre o maior valor em qualquer subarray de tamanho K.

Ou:

Calcule a média máxima de uma sequência de tamanho K.

Ou:

Encontre a soma máxima de K elementos consecutivos.

8. Sliding Window de tamanho variável

Existe outro tipo de Sliding Window.

Nesse caso, o tamanho da janela pode aumentar ou diminuir.

Imagine:

[2, 3, 1, 2, 4, 3]

Queremos encontrar o menor subarray cuja soma seja pelo menos:

target = 7

Temos:

[2, 3, 1, 2, 4, 3]

Começamos aumentando a janela.

[2]

Soma:

2

Ainda não chegou em 7.

Expandimos:

[2, 3]

Soma:

5

Expandimos:

[2, 3, 1]

Soma:

6

Expandimos:

[2, 3, 1, 2]

Soma:

8

Agora atingimos o objetivo.

Podemos tentar diminuir a janela:

[3, 1, 2]

Soma:

6

Ficou menor que 7.

Então precisamos expandir novamente.

A menor janela encontrada foi:

[2, 3, 1, 2]

com tamanho:

4

9. Implementação da janela variável

function minSubArrayLen(
  target: number,
  numbers: number[]
): number {
  let left = 0;
  let sum = 0;
  let minLength = Infinity;

  for (
    let right = 0;
    right < numbers.length;
    right++
  ) {
    sum += numbers[right];

    while (sum >= target) {
      minLength = Math.min(
        minLength,
        right - left + 1
      );

      sum -= numbers[left];
      left++;
    }
  }

  return minLength === Infinity
    ? 0
    : minLength;
}

Uso:

const result = minSubArrayLen(
  7,
  [2, 3, 1, 2, 4, 3]
);

console.log(result);

Resultado:

2

Porque existe:

[4, 3]

E:

4 + 3 = 7

Portanto, a menor janela possui tamanho 2.

10. Como funciona a janela variável?

Temos dois ponteiros:

left
right

O right expande a janela:

right++

O left reduz a janela:

left++

A lógica é:

Adicionar elemento pelo right
          ↓
      Soma aumentou
          ↓
Objetivo foi atingido?
          ↓
        Sim
          ↓
Tentar remover pelo left
          ↓
Encontrar uma janela menor

Visualmente:

left                right
 ↓                     ↓
[2, 3, 1, 2, 4, 3]

Quando a condição é satisfeita:

    left            right
     ↓                ↓
[2, 3, 1, 2, 4, 3]

Movemos left:

       left         right
        ↓             ↓
[2, 3, 1, 2, 4, 3]

Continuamos até a condição deixar de ser válida.

11. O padrão visual

Podemos resumir a janela variável assim:

             Expandir
                ↓
        ┌───────────────┐
        │    WINDOW     │
        └───────────────┘
         ↑             ↑
       left           right
         │             │
         └─────────────┘
                │
                ▼
       Condição satisfeita?
          /           \
        Não            Sim
         │              │
         │              ▼
         │        Tentar reduzir
         │              │
         └──────────────┘

O segredo é saber quando expandir e quando reduzir.

12. Sliding Window em Strings

Sliding Window também é extremamente útil para strings.

Um problema clássico é:

Encontre o tamanho da maior substring sem caracteres repetidos.

Por exemplo:

abcabcbb

A maior substring sem repetição é:

abc

Tamanho:

3

13. Pensando como uma janela

Começamos:

[a]

Depois:

[ab]

Depois:

[abc]

O próximo caractere é:

a

Mas a já está dentro da janela.

Então precisamos remover elementos da esquerda:

abcabcbb
↑

Removemos:

a

Agora:

[bc]

Podemos adicionar o novo a:

[bca]

Continuamos.

A janela sempre representa uma substring válida, sem duplicatas.

14. Implementação

function lengthOfLongestSubstring(
  s: string
): number {
  const seen = new Set<string>();

  let left = 0;
  let maxLength = 0;

  for (
    let right = 0;
    right < s.length;
    right++
  ) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }

    seen.add(s[right]);

    maxLength = Math.max(
      maxLength,
      right - left + 1
    );
  }

  return maxLength;
}

Uso:

const result =
  lengthOfLongestSubstring("abcabcbb");

console.log(result);

Resultado:

3

A substring encontrada é:

abc

15. Visualizando

Começamos:

abcabcbb
↑
L
↑
R

Janela:

[a]

Expandimos:

abcabcbb
↑ ↑
L R

Janela:

[ab]

Expandimos:

abcabcbb
↑   ↑
L   R

Janela:

[abc]

Encontramos:

maxLength = 3

Agora aparece outro a:

[abca]

Inválido.

Removemos da esquerda:

a [bca]

Agora:

[bca]

A janela voltou a ser válida.

16. Um exemplo prático: análise de acessos

Imagine que você está monitorando acessos a uma API:

timestamps

E deseja descobrir:

Qual foi o maior número de requisições realizadas dentro de qualquer intervalo de 60 segundos?

Se os timestamps forem:

[1, 5, 10, 20, 30, 70, 80]

Podemos manter uma janela contendo apenas os acessos dentro dos últimos 60 segundos.

Começamos:

[1, 5, 10, 20, 30]

Depois chega:

70

O timestamp 1 está fora da janela de 60 segundos.

Removemos:

[5, 10, 20, 30, 70]

Depois:

80

A janela passa a ser:

[20, 30, 70, 80]

Esse padrão é muito útil para sistemas de:

• Rate limiting
• Monitoramento
• Métricas
• Analytics
• Logs
• Detecção de picos de tráfego

17. Exemplo de Rate Limiting

Imagine uma API que permite:

100 requisições por minuto

Podemos armazenar os timestamps das requisições.

Por exemplo:

const requests = [
  1000,
  1005,
  1010,
  1020,
  1050
];

Quando uma nova requisição chega:

timestamp = 1060

Podemos remover da esquerda todas as requisições que ficaram fora da janela de 60 segundos.

A lógica seria:

while (
  requests.length > 0 &&
  requests[0] < timestamp - 60
) {
  requests.shift();
}

Depois:

if (requests.length >= 100) {
  return "Rate limit exceeded";
}

requests.push(timestamp);

Em sistemas reais, essa lógica geralmente é implementada com estruturas mais eficientes, como Redis, mas o conceito de Sliding Window é o mesmo.

18. Fixed Window vs Variable Window

Podemos dividir os problemas em dois grandes grupos.

Fixed Window

O tamanho é conhecido:

k = 3

Exemplo:

[1, 2, 3]
 [2, 3, 4]
  [3, 4, 5]

Normalmente queremos:

• Maior soma
• Menor soma
• Média
• Máximo
• Mínimo

Variable Window

O tamanho muda conforme uma condição.

Exemplo:

Soma >= target

Ou:

Não existem caracteres duplicados

A janela cresce:

right++

E pode diminuir:

left++

19. Sliding Window vs Two Pointers

As duas técnicas são parecidas.

Na verdade, Sliding Window frequentemente utiliza uma ideia semelhante a Two Pointers.

Two Pointers

Normalmente temos dois índices independentes:

left
right

Eles podem se mover conforme diferentes regras.

Exemplo:

[1, 2, 3, 4, 5]
 ↑           ↑
left       right

Sliding Window

Os dois ponteiros representam os limites de uma janela:

[1, 2, 3, 4, 5]
 ↑───────↑
 left   right

Tudo que está entre eles faz parte da janela atual.

A principal diferença conceitual é:

Two Pointers
→ Dois ponteiros para navegar ou comparar posições.

Sliding Window
→ Dois ponteiros delimitando um intervalo que representa uma solução parcial.

Por isso, Sliding Window pode ser visto como um padrão especializado de Two Pointers.

20. Como reconhecer Sliding Window?

Algumas palavras-chave podem indicar que o problema pode utilizar essa técnica.

Procure por expressões como:

"subarray"
"substring"
"contiguous"
"consecutive"
"window"
"longest"
"shortest"
"maximum"
"minimum"

Por exemplo:

Encontre a maior substring sem caracteres repetidos.

Pode indicar:

Sliding Window

Ou:

Encontre a maior soma de K elementos consecutivos.

Pode indicar:

Fixed Sliding Window

Ou:

Encontre o menor subarray cuja soma seja pelo menos target.

Pode indicar:

Variable Sliding Window

21. A pergunta que você deve fazer

Quando encontrar um problema desse tipo, pergunte:

Existe um intervalo contínuo que eu posso expandir e reduzir sem recalcular tudo?

Se a resposta for sim, Sliding Window pode ser uma boa abordagem.

A estrutura normalmente será:

let left = 0;

for (
  let right = 0;
  right < array.length;
  right++
) {
  // Adiciona array[right]

  while (condição inválida) {
    // Remove array[left]
    left++;
  }

  // Atualiza resposta
}

Esse é um dos templates mais importantes para memorizar.

22. O grande benefício

Sem Sliding Window, podemos acabar recalculando:

[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
[4, 5, 6]

Cada janela do zero.

Com Sliding Window:

[1, 2, 3]
      ↓
remove 1
add 4
      ↓
[2, 3, 4]
      ↓
remove 2
add 5
      ↓
[3, 4, 5]

A janela é atualizada incrementalmente.

Não precisamos começar do zero a cada vez.

Conclusão

Sliding Window é uma técnica utilizada para trabalhar com intervalos contínuos de arrays e strings.

A ideia é manter uma janela delimitada por dois ponteiros:

left                 right
 ↓                      ↓
[────── WINDOW ─────────]

Podemos ter dois principais tipos.

Janela fixa

Tamanho = K

Utilizada para problemas como:

Maior soma de K elementos
Maior média de K elementos

Janela variável

Tamanho muda

Utilizada para problemas como:

Menor subarray que satisfaz uma condição
Maior substring sem duplicatas

O padrão geral é:

Expandir a janela
       ↓
Verificar condição
       ↓
Se necessário, reduzir
       ↓
Atualizar resposta

A grande vantagem é evitar recalcular informações que já temos.

Em vez de:

O(n²)

podemos frequentemente chegar a:

O(n)

A principal lição é:

Quando o problema envolve uma sequência contínua e você precisa encontrar o maior, menor ou melhor intervalo que satisfaz determinada condição, pense em Sliding Window.