Padrões para Quebrar a Banca: Two Pointers, Sliding Window e Mais
Aprenda a reconhecer e aplicar padrões de resolução de problemas como Two Pointers, Sliding Window e Prefix Sum para otimizar suas soluções em entrevistas.
Sabe quando você está travado em um problema de entrevista, a solução de força bruta é lenta demais, e você não sabe como otimizar? Muitas vezes, a resposta não é uma estrutura de dados nova e complexa, mas sim uma técnica, um padrão de como percorrer os dados.
Aprender a reconhecer esses padrões é como ter um molho de chaves mestras. Em vez de testar chaves aleatórias, você olha para a fechadura (o problema) e já sabe qual chave usar.
Nesta aula, vamos dominar três dos padrões mais poderosos e comuns para problemas com arrays e strings: Two Pointers, Sliding Window e Prefix Sum. Eles são o "pulo do gato" que transforma soluções O(n²) em O(n).
1. O Padrão dos Dois Ponteiros (Two Pointers) ↔️
É uma técnica extremamente comum onde usamos dois ponteiros (geralmente índices de um array) que se movem pela coleção de dados até encontrarem uma condição ou até se cruzarem.
Quando Usar?
Exemplo Clássico: "Two Sum" em Array Ordenado
// Problema: Dado um array ORDENADO, encontre um par que some 'target'.
function twoSumSorted(arr, target) {
let left = 0; // Ponteiro no início
let right = arr.length - 1; // Ponteiro no final
while (left < right) {
const currentSum = arr[left] + arr[right];
if (currentSum === target) {
return [arr[left], arr[right]]; // Encontrou!
} else if (currentSum < target) {
// A soma é pequena demais, precisamos de um número maior.
left++;
} else {
// A soma é grande demais, precisamos de um número menor.
right--;
}
}
return null; // Nenhum par encontrado
}
// Complexidade de Tempo: O(n)
// Complexidade de Espaço: O(1)2. O Padrão da Janela Deslizante (Sliding Window) 🖼️
Este padrão é usado para percorrer uma porção específica de dados em um array ou string, geralmente para encontrar o subarray ou substring "ótima" que satisfaz uma condição. A "janela" (um subarray contíguo) desliza sobre os dados, expandindo e contraindo conforme necessário.
Quando Usar?
Exemplo Clássico: Soma Máxima de Subarray de Tamanho 'K'
// Problema: Encontre a soma máxima de qualquer subarray contíguo de tamanho 'k'.
function maxSumSubarray(arr, k) {
// Adiciona uma verificação para entradas inválidas para tornar o código mais robusto.
if (k <= 0 || arr.length < k) {
return null; // ou 0, ou lançar um erro, dependendo do comportamento desejado
}
let maxSum = -Infinity;
let windowSum = 0;
let windowStart = 0;
for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
// Adiciona o próximo elemento à janela
windowSum += arr[windowEnd];
// "Desliza" a janela quando ela atingir o tamanho 'k'
if (windowEnd >= k - 1) {
maxSum = Math.max(maxSum, windowSum); // Atualiza a soma máxima
// Subtrai o elemento que está saindo da janela
windowSum -= arr[windowStart];
// Move o início da janela para a frente
windowStart++;
}
}
return maxSum;
}
// Complexidade de Tempo: O(n)
// Complexidade de Espaço: O(1)A mágica aqui é que, a cada passo, em vez de recalcular a soma de toda a nova janela, nós simplesmente subtraímos o elemento que saiu e adicionamos o que entrou, mantendo a operação em O(1) e o total em O(n).
3. O Padrão da Soma de Prefixo (Prefix Sum) ⚡
Este padrão é uma ferramenta poderosa de pré-computação. A ideia é criar um array auxiliar onde cada posição `i` contém a soma de todos os elementos do array original de `0` até `i`.
Quando Usar?
Exemplo Clássico: Range Sum Query
A mágica está na fórmula: soma(i, j) = prefixSum[j] - prefixSum[i-1].
// Problema: Responda rapidamente a múltiplas consultas pela soma de um intervalo [i, j].
class NumArray {
constructor(nums) {
// 1. Pré-computação em O(n)
this.prefixSum = [0];
for (const num of nums) {
this.prefixSum.push(this.prefixSum[this.prefixSum.length - 1] + num);
}
}
// 2. Consulta em O(1)
sumRange(left, right) {
// sum(i, j) = prefixSum[j+1] - prefixSum[i]
return this.prefixSum[right + 1] - this.prefixSum[left];
}
}
// const numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
// numArray.sumRange(0, 2); // -> 1 (-2 + 0 + 3)
// numArray.sumRange(2, 5); // -> -1 (3 + -5 + 2 + -1)💊 Pílula Devly
Estruturas de dados são seus ingredientes. Padrões como Two Pointers, Sliding Window e Prefix Sum são suas receitas secretas. Aprender a reconhecer os "sintomas" de um problema e aplicar o padrão correto é o que te transforma de um bom cozinheiro em um chef de cozinha nas entrevistas.