Two Pointers
Dois ponteiros é a ideia mais simples de otimização de array: em vez de dois laços aninhados (O(n²)), você usa dois índices que caminham de forma coordenada e resolve em uma passada, O(n).
O padrão
Existem dois sabores principais:
- Convergentes, um ponteiro na ponta esquerda, outro na direita, e eles se aproximam. Clássico em array ordenado: "existe um par que soma o alvo?", "container com mais água", palíndromo.
- Na mesma direção, os dois começam à esquerda e avançam em ritmos diferentes (lento/rápido). É o motor da Sliding Window e de detecção de ciclo em listas ligadas.
Aqui vamos ao caso convergente, que é o mais visual.
Two Sum num array ordenado
Dado um array ordenado e um alvo, ache dois números que somem o alvo. Como está ordenado, você não precisa testar todos os pares: se a soma atual for grande demais, o único jeito de diminuir é recuar a direita; se for pequena demais, avançar a esquerda. Cada passo elimina uma coluna inteira de possibilidades.
Rode abaixo, repare como o espaço de busca (as células acesas) encolhe a cada passo. Use Expandir para ver o código lado a lado.
esquerda no início, direita no fim do array ordenado.
Por que funciona
O array estar ordenado é o que dá o direito de mover só um ponteiro por vez sem perder soluções:
- Se
soma < alvo, nenhum par usando a direita atual com um índice ainda menor que a esquerda serviria (todos seriam ≤ a soma atual). Então a direita está "gasta" para esse esquerda, avança a esquerda. - Se
soma > alvo, simetricamente, a esquerda atual não fecha com nenhuma direita ainda maior. Recua a direita.
Cada índice é visitado no máximo uma vez → O(n) tempo, O(1) espaço.
Precisa estar ordenado. Se o array não estiver ordenado e você não puder ordenar (porque os índices originais importam), dois ponteiros convergentes não valem, aí o caminho costuma ser um hashmap de complementos.
Vídeo da aula
Direto do canal da comunidade Craft & Code Club · 16:40.
Problemas para praticar
Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.
Referências
Artigos e materiais externos para se aprofundar.
Travou em algum passo? Traga sua questão para o Discord da comunidade ou para os encontros semanais.
Entrar