Dois Ponteiros: Extremidades Opostas
Use ponteiros esquerdo e direito que avançam um em direção ao outro para resolver soma de pares em arrays ordenados, palíndromos válidos e retenção de água da chuva.
Dois Ponteiros: Extremidades Opostas é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
A Ideia dos Dois Ponteiros
A técnica de dois ponteiros usa duas variáveis de índice que se movem uma em direção à outra (ou na mesma direção) para reduzir a necessidade de laços aninhados. Em vez de verificar cada par em O(n²), você avança with cada comparação e termina em O(n). Quase sempre é necessário que o vetor esteja ordenado primeiro, pois a ordenação permite determinar em que direção mover cada ponteiro com base no fato de a soma do par atual ser grande ou pequena demais.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []Dois Ponteiros em um Vetor Ordenado
Com um vetor ordenado, coloque um ponteiro na extremidade esquerda (o menor elemento) e outro na extremidade direita (o maior elemento). Se a soma for pequena demais, mova o ponteiro esquerdo para a direita para aumentá-la. Se a soma for grande demais, mova o ponteiro direito para a esquerda para diminuí-la. Cada iteração avança pelo menos um ponteiro, portanto o laço executa no máximo n vezes: O(n) no total após a ordenação. É importante observar que cada movimento é comprovadamente correto devido à ordem do vetor.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Verificação de Palíndromo Válido
Uma cadeia de caracteres é um palíndromo se for lida da mesma forma para frente e para trás. Use dois ponteiros, começando nas duas extremidades e avançando para o centro: compare os caracteres, ignore os caracteres não alfanuméricos e pare quando os ponteiros se cruzarem. Isso leva O(n) e usa espaço adicional O(1) — é muito mais simples que inverter a cadeia de caracteres e compará-la, o que aloca O(n) de memória adicional.
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseSoma de Três Elementos: Ordenação + Dois Ponteiros
O problema da soma de três elementos pede todos os trios distintos cuja soma seja zero. Ordene o vetor, fixe cada elemento nums[i] e execute uma busca com dois ponteiros no subvetor restante por um par cuja soma seja -nums[i]. Ignore duplicatas tanto do elemento fixado quanto do par encontrado para evitar trios repetidos. Tempo total: O(n²) após a ordenação O(n log n).
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Recipiente com Mais Água
Dadas as alturas de linhas verticais, encontre duas linhas que formem um recipiente capaz de conter a maior quantidade de água. Área = min(height[left], height[right]) × (right - left). Mova de forma gulosa para dentro o ponteiro na linha mais curta: mover a linha mais alta só pode reduzir a largura sem aumentar o limite de altura. Essa escolha gulosa é comprovadamente ideal e oferece tempo O(n).
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Elevando ao Quadrado um Vetor Ordenado
Eleve ao quadrado cada elemento de um vetor ordenado (que pode conter números negativos) e retorne o resultado em ordem crescente. Os quadrados de números negativos são grandes; os quadrados de números positivos são pequenos no centro. Posicione dois ponteiros nas extremidades e preencha o vetor de resultado da direita para a esquerda (do maior para o menor). Tempo O(n) e espaço de saída O(n) — muito melhor do que elevar ao quadrado e depois ordenar em O(n log n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Captura de Água da Chuva
A água acumulada no índice i é igual a min(max_left, max_right) - height[i]. Abordagem de dois ponteiros: mantenha os valores máximos acumulados max_left e max_right. Quando max_left < max_right, o lado esquerdo é o gargalo — processe o ponteiro esquerdo. Caso contrário, processe o direito. Isso elimina a necessidade de vetores separados do máximo à esquerda e do máximo à direita, alcançando espaço adicional O(1).
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Por que o Movimento Guloso do Ponteiro Funciona
Uma pergunta comum de acompanhamento em entrevistas é: por que é seguro descartar o ponteiro menor? Esboço da prova para o problema do recipiente com mais água: suponha que height[left] < height[right]. Todo par formado pela posição esquerda e por uma posição j < posição direita tem área ≤ altura da posição esquerda × (posição direita − posição esquerda) ≤ área atual. Portanto, nenhum par que comece na posição esquerda e use um índice direito menor que o índice da direita pode superar a área atual. Podemos ignorá-los com segurança avançando o ponteiro esquerdo.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Par de diferença mínima em vetor ordenado
Encontre o par de números em um vetor ordenado com a menor diferença absoluta. Use dois ponteiros adjacentes (não em extremidades opostas) que percorram juntos: |nums[i] - nums[i+1]| para todos os pares consecutivos. A diferença mínima em um vetor ordenado sempre ocorre entre elementos adjacentes (porque a ordenação agrupa valores próximos). Isso é O(n) após a ordenação.
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Modelo de dois ponteiros em extremidades opostas
A maioria dos problemas de dois ponteiros em extremidades opostas segue a mesma estrutura. Dominar este modelo permite adaptá-lo rapidamente sob pressão de tempo. As decisões principais são: (1) qual condição faz a esquerda avançar, (2) qual condição faz a direita avançar, (3) o que constitui uma solução e (4) como lidar com duplicatas. Pratique codificar essas decisões a partir do enunciado antes de escrever qualquer código.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultContagem de pares válidos com dois ponteiros
Dois ponteiros também permitem contar pares com eficiência. Para o problema “contar pares cuja soma < alvo” em um vetor ordenado: fixe o ponteiro esquerdo e use o ponteiro direito para encontrar o índice direito válido mais à direita. Todos os pares (esquerda, esquerda+1 até direita) são válidos — adicione right - left à contagem e avance a esquerda. Isso conta todos os pares válidos em O(n), em vez de O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: ponteiros de extremidades opostas substituem a enumeração de pares O(n²) pela convergência da esquerda para a direita em O(n) em vetores ordenados, a decisão de qual ponteiro avançar decorre da propriedade monótona do problema — mova o lado que atualmente limita o progresso e a soma de três valores, o recipiente com mais água, a retenção de água da chuva e a verificação de palíndromos reduzem-se ao mesmo modelo central. A seguir, exploraremos os padrões de ponteiros lento e rápido.
Perguntas Frequentes
A aula “Dois Ponteiros: Extremidades Opostas” é grátis?
Sim — o texto completo de “Dois Ponteiros: Extremidades Opostas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Dois Ponteiros: Extremidades Opostas”?
Use ponteiros esquerdo e direito que avançam um em direção ao outro para resolver soma de pares em arrays ordenados, palíndromos válidos e retenção de água da chuva. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Dois Ponteiros: Extremidades Opostas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Fundamentos de Arrays e Operações In-Place
- Somas de Prefixos e Totais Acumulados
- Dois Ponteiros: Extremidades Opostas
- Dois Ponteiros: Lento e Rápido