Encontra dois números que somam ao valor alvo usando hash map para busca O(1).
Two Sum é um clássico de entrevistas. O problema: dado um array e um valor alvo, encontre dois números que somam a esse valor. A solução ingênua usa dois loops — O(n²). Mas com um hash map, resolvemos em O(n). A sacada é perceber que, para cada número, sabemos exatamente qual outro número precisamos: o complemento (target - número atual). Em vez de procurar esse complemento com outro loop, guardamos os números já vistos em um hash map. Busca em hash map é O(1).
“O hash map transforma busca O(n) em O(1). É a diferença entre O(n²) e O(n).”
Uma passada pelo array. Cada lookup no hash map é O(1).
n iterações × O(1) por iteração = O(n).
O hash map pode guardar até n elementos no pior caso.
Se os dois primeiros elementos formam o par.
O par está no final ou não existe.
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| Two Sum (Hash Map)(atual) | O(n) | O(n) | Array não ordenado |
| Two Sum (Dois Ponteiros) | O(n) | O(1) | Array já ordenado |
| Two Sum (Força Bruta) | O(n²) | O(1) | Entender o problema |
| Three Sum | O(n²) | O(1) | Encontrar triplas que somam zero |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1def two_sum(nums, target):Definição2 seen = {}Hash Map3 4 for i, num in enumerate(nums):Enumerate5 complement = target - numComplemento6 7 if complement in seen:Busca8 return [seen[complement], i]9 10 seen[num] = iArmazenar11 12 return NoneNão Encontrado13