Problema Two Sum em Python
Nesta lição, você vai resolver o problema Two Sum, encontrando dois elementos cuja soma é um valor dado com uma única passada pela lista.
Introdução
O problema
Dada uma lista de preços e um orçamento, quais dois itens custam exatamente o orçamento? Testar cada par funciona, mas leva cerca de n² / 2 comparações. Se você lembrar o que já viu, dá para resolver em uma passada.
Pense assim
O Two Sum é como fazer compras com um orçamento exato. Para cada etiqueta de preço, você calcula quanto ainda falta e confere suas anotações: já vi algum produto exatamente com esse preço? Se sim, o par foi encontrado. Se não, você anota esse preço e onde o viu, e segue em frente.
complement = target - value🤔 O preço que ainda faltaif complement in seen:📋 Esse preço já está nas minhas anotações?return [seen[complement], index]🛍️ Achei o par: as duas posiçõesseen[value] = index✍️ Anote este preço e a posição dele, e continueO problema Two Sum pede as posições de dois números de uma lista que somam um alvo. Um dicionário com os valores já vistos resolve em uma passada, em tempo O(n).
Pontos-chave
complement = target - valueé o valor que completaria o par.seenassocia cada valor já visitado ao seu índice, então as consultas são rápidas.if complement in seen:encontra o par entre os valores anteriores.seen[value] = indexé guardado depois da verificação, então um valor nunca forma par consigo mesmo.- Para 9, o valor 7 encontra seu par 2 no índice 0, dando
[0, 1].
Quando usar?
- Encontrar pares com uma soma ou diferença dada.
- Aprender a trocar memória por velocidade com uma tabela hash.
- Uma pergunta de entrevista muito comum e a base do 3-Sum e de problemas parecidos.
Quando não é preciso
- Entrada ordenada com memória apertada: dois ponteiros, um em cada ponta, não usam memória extra.
- Você precisa de todos os pares, não só de um: junte os resultados em vez de devolver na primeira correspondência.
Código de exemplo
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
Resultado da execução
[0, 1]
Explicação do código
O dicionário seen guarda os valores já percorridos junto com suas posições. Para cada elemento, o programa calcula o complemento complement = target - value e verifica se ele já está em seen. Como a busca em dicionário leva O(1), o algoritmo todo roda em O(n) e usa O(n) de memória extra.
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Guardar antes de verificar
Um valor pode formar par consigo mesmo, como 3 + 3 = 6 com um único 3.
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
Todos os desafios