Algoritmos em Python

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.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

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.

Das compras com orçamento ao código
complement = target - value🤔 O preço que ainda falta
if complement in seen:📋 Esse preço já está nas minhas anotações?
return [seen[complement], index]🛍️ Achei o par: as duas posições
seen[value] = index✍️ Anote este preço e a posição dele, e continue
Procure o preço que falta em vez de testar todos os pares.
Em uma frase

O 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

  1. complement = target - value é o valor que completaria o par.
  2. seen associa cada valor já visitado ao seu índice, então as consultas são rápidas.
  3. if complement in seen: encontra o par entre os valores anteriores.
  4. seen[value] = index é guardado depois da verificação, então um valor nunca forma par consigo mesmo.
  5. 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

Executar código →
main.py
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))
Gerar um botão Run para este exemplo

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.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Guardar antes de verificar

Um valor pode formar par consigo mesmo, como 3 + 3 = 6 com um único 3.

Problema
seen[value] = index
if target - value in seen:
Correção
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