Padrão 1: Hash Map
O padrão mais usado do LeetCode. A ideia cabe numa frase: troque memória por tempo, lembrando o que você já viu.
Tente primeiro: Two Sum
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dado um array nums e um número target, retorne os índices de dois números que somam target. Existe exatamente uma resposta.
Exemplo: nums = [2, 7, 11, 15], target = 9 → [0, 1] (porque 2 + 7 = 9).
Tentou? Se foi pela solução "óbvia" — para cada número, varrer o resto do array atrás do complemento — você escreveu a força bruta: dois laços aninhados, O(n²). Ela funciona, mas repete uma busca a cada passo. A teoria abaixo mostra como eliminar esse desperdício.
A teoria: que problema o hash map resolve?
Um array é ótimo em responder "o que existe na posição i?" — custo O(1). Mas é péssimo em responder a pergunta inversa: "o valor x existe? onde?" — custo O(n), porque é preciso olhar item por item.
O hash map (dicionário do Python, objeto/Map do JS) inverte a pergunta: ele indexa pelo valor, não pela posição. Com ele, "já vi x? onde?" custa O(1) em média.
Por que O(1)? A intuição: o hash map calcula, a partir do valor, em qual gaveta ele estaria (a função de hash) — e vai direto na gaveta, sem procurar. É como saber a estante exata do livro pela ficha catalográfica, em vez de varrer a biblioteca.
Os sinais no enunciado
Pense em hash map quando o problema pedir alguma dessas perguntas, repetidas muitas vezes:
- "Existe um par que..." — para cada elemento, procuro um complemento (soma, diferença, dobro...).
- "Tem repetido? Quantas vezes aparece?" — contar ou detectar duplicatas.
- "Agrupe os que..." — agrupar por alguma característica.
- O enunciado pede uma única passada ou tempo O(n) num problema que parece exigir comparações de pares.
O template mental
Quase toda solução com hash map tem este formato:
mapa = vazio
para cada elemento x do array:
1. PERGUNTE ao mapa o que você precisa saber sobre o passado
("já vi o complemento de x?", "quantos x já vi?")
2. Se a resposta resolve o problema → pronto
3. REGISTRE x no mapa para o futuro
O pulo do gato: perguntar antes de registrar. Assim cada elemento é comparado só com o passado, cada par é considerado exatamente uma vez, e uma única passada basta.
Exemplo 1 — Two Sum (o cartão de visitas do padrão)
"Dado um array e um alvo, retorne os índices de dois números que somam o alvo."
Aplicando o método da aula anterior:
- Força bruta: para cada
nums[i], varrer o resto atrás dealvo - nums[i]. São todos os pares: O(n²) — espaço O(1). - O desperdício: a busca pelo complemento refaz, a cada volta, um trabalho de O(n) sobre valores que já passaram pelos nossos olhos.
- O padrão: guarde cada valor visto (e seu índice) num hash map. A busca pelo complemento vira uma consulta O(1).
Veja a solução rodando passo a passo — repare que o mapa seen só cresce
com o passado, e a pergunta vem sempre antes do registro:
Por que é O(n)? (justificando, como prometido)
- O loop roda n vezes — uma por elemento.
- Dentro dele só há operações de hash map (
in/consulta/inserção), cada uma O(1) em média (regra 4 da seção de fundamentos). - n voltas × O(1) = O(n) de tempo.
- O mapa pode acabar guardando todos os n elementos = O(n) de espaço.
Compare: a força bruta era O(n²) de tempo com O(1) de espaço. O hash map comprou tempo pagando memória — o trade-off da aula de fundamentos, acontecendo na prática.
| Solução | Tempo | Espaço | Por quê |
|---|---|---|---|
| Força bruta | O(n²) | O(1) | testa todos os pares |
| Hash map | O(n) | O(n) | 1 passada × consultas O(1) |
Exemplo 2 — Contains Duplicate
"O array tem algum valor repetido?" — é o padrão na sua forma mais pura: a pergunta ao passado é simplesmente "já vi você?".
Implemente você mesmo no editor abaixo (esqueleto pronto). Dica: aqui não precisamos de índices, então um set (hash map só de chaves) basta.
Alternativa que vale conhecer: ordenar e olhar vizinhos — duplicatas ficam lado a lado. Tempo O(n log n) (o sort domina), espaço O(1). É o trade-off invertido: economiza memória pagando tempo.
| Solução | Tempo | Espaço |
|---|---|---|
| Força bruta (todos os pares) | O(n²) | O(1) |
| Sort + vizinhos | O(n log n) | O(1) |
| Hash set | O(n) | O(n) |
Onde mais esse padrão aparece
Você vai reencontrar o hash map em Group Anagrams e Valid Anagram (seção String — agrupando e contando), no Subarray Sum Equals K (combinado com prefix, aula 5) e em metade dos problemas de grafos (guardando visitados). É o canivete suíço do curso.
🧠 Quiz de fixação
0/41. No template do padrão, por que perguntar ao mapa ANTES de registrar o elemento atual?
2. Por que a solução do Two Sum com hash map é O(n) e não O(n²)?
3. Para Contains Duplicate, a solução 'ordenar e comparar vizinhos' (O(n log n), O(1) de espaço) faz sentido quando...
4. Enunciado novo: 'encontre dois números cuja DIFERENÇA é k'. Como o padrão hash map se aplica?
Resumo
- Hash map responde "já vi x? onde? quantas vezes?" em O(1) médio — array responde isso em O(n).
- Template: pergunte ao passado → registre para o futuro, nessa ordem.
- Sinais: pares com complemento, duplicatas, contagem, agrupamento, "uma passada só".
- Custo: tempo O(n), espaço O(n) — memória comprando tempo.
Próxima aula: quando o desperdício não é busca repetida, mas comparar pares que não têm chance — two pointers.