Pular para o conteúdo

Dois ponteiros

Aula 2 de 14 · 5 min

Dois ponteiros

Passo 1 de 9

O array está ordenado, então comece o mais aberto possível: um ponteiro em cada ponta.

A ideia

Mantenha um índice em cada ponta e mova os dois um em direção ao outro conforme o que você vê. Cada passo descarta um grupo inteiro de pares de uma vez. A força bruta confere cada par em O(n²); a técnica de dois ponteiros (two pointers) faz o mesmo trabalho em O(n).

Exemplo do mundo real

Duas pessoas procuram um par de volumes que combinam em uma estante comprida, cada uma começando em uma ponta e seguindo em direção ao meio. Elas se encontram no centro depois de percorrer a estante exatamente uma vez, em vez de uma delas refazer todo o percurso para cada livro.

O código

Sua vez

O que isto imprime?

nums = [2, 5, 9]
l, r = 0, 2
while l < r:
  print(nums[l] + nums[r])
  l += 1
  r -= 1

Mini quiz

1 / 3

Em uma entrada ordenada, dois ponteiros transformam uma busca de pares O(n²) em: