Caminhe para dentro com dois ponteiros
Use dois índices para resolver problemas de arrays ordenados e palíndromos em O(n).
- Reconhecer quando os dois ponteiros se aplicam.
- Mover os ponteiros com base numa comparação.
- Resolver problemas de soma de pares em entrada ordenada sem espaço extra.
O padrão de dois ponteiros mantém dois índices numa sequência e os move um em direção ao outro (ou na mesma direção) de acordo com o que eles veem. Ele costuma transformar uma busca de pares O(n²) em O(n), com O(1) de espaço extra. O requisito principal é uma estrutura que você possa explorar - na maioria das vezes, uma entrada ordenada.
Como os ponteiros se movem
- Pontas opostas: comece em
left = 0eright = n - 1. Para uma soma de pares em entrada ordenada: se a soma for pequena demais, movaleftpara a direita para aumentá-la; se for grande demais, movarightpara a esquerda. - Palíndromos: compare os caracteres das duas pontas e avance para dentro.
- Mesma direção (rápido/lento): um ponteiro lê, o outro escreve - usado para remover duplicatas no próprio array ou particionar um array.
1def is_palindrome(text):
2 chars = [c.lower() for c in text if c.isalnum()]
3 left, right = 0, len(chars) - 1
4 while left < right:
5 if chars[left] != chars[right]:
6 return False
7 left += 1
8 right -= 1
9 return True
10
11print(is_palindrome("A man, a plan, a canal: Panama"))
12print(is_palindrome("race a car"))True False
Por que é seguro mover um ponteiro? Numa busca de pares ordenada, se nums[left] + nums[right] for pequeno demais, então nums[left] com qualquer elemento até right também é pequeno demais, então left nunca pode fazer parte da resposta - descarte-o. Conseguir dizer isso em voz alta é o que convence o entrevistador de que a sua solução está correta.
Principais conclusões
Dois ponteiros transformam muitas buscas de pares O(n²) em O(n).
Entrada ordenada é o sinal mais comum.
Esteja pronto para justificar por que cada movimento de ponteiro é seguro.
Quiz da aula
5 perguntas · aprovação com 4 acertos · até 50 XP
Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.
Pratique: resolva problemas de entrevistas técnicas
Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.
Encontre um par num array ordenado
Leia uma linha de inteiros em ordem crescente e depois um alvo. Usando dois ponteiros, imprima os índices (a partir de 0) de um par que soma o alvo (o menor índice primeiro), ou none se esse par não existir.
- O par existe
- Sem par
O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.
Dúvidas sobre esta lição
Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.
Carregando publicações…