Two Sum

“Este desafio é apenas um warm-up. Os próximos desafios focam em problemas reais de sistemas backend.”

🧩 Problema

Dado um array de inteiros nums e um inteiro target, retorne os índices dos dois números que somam o valor target.

Você pode assumir que cada entrada tem exatamente uma solução, e você não pode usar o mesmo elemento duas vezes.

Você pode retornar a resposta em qualquer ordem.

Exemplo 1:

Exemplo 2:

Exemplo 3:

Restrições:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Apenas uma resposta válida existe

💡 Abordagem

Solução Ingênua (Força Bruta)

A abordagem mais simples seria verificar todos os pares possíveis usando dois loops aninhados. Para cada elemento, verificaríamos se existe outro elemento que soma ao target. Esta solução tem complexidade O(n²).

Solução Otimizada (Hash Map)

Podemos resolver este problema em uma única passagem usando um hash map (ou dicionário):

1. Ideia principal: Para cada número num no array, verificamos se o complemento target - num já foi visto anteriormente
2. Estrutura de dados: Usamos um hash map para armazenar os números já vistos e seus índices
3. Algoritmo:
   • Iteramos pelo array uma vez
   • Para cada elemento, calculamos o complemento necessário
   • Se o complemento já está no hash map, encontramos a solução
   • Caso contrário, adicionamos o número atual ao hash map

Por que Hash Map?

• Busca em O(1) em média
• Armazenamento do índice junto com o valor
• Evita a necessidade de loops aninhados

🧪 Solução

Solução em Go

1func twoSum(nums []int, target int) []int {
2    // Hash map para armazenar valor -> índice
3    seen := make(map[int]int)
4
5    for i, num := range nums {
6        complement := target - num
7
8        // Verificar se o complemento já foi visto
9        if idx, found := seen[complement]; found {
10            return []int{idx, i}
11        }
12
13        // Armazenar o número atual e seu índice
14        seen[num] = i
15    }
16
17    // Não deveria chegar aqui dado que há garantia de solução
18    return nil
19}

Solução em TypeScript

1function twoSum(nums: number[], target: number): number[] {
2    const seen = new Map<number, number>();
3
4    for (let i = 0; i < nums.length; i++) {
5        const complement = target - nums[i];
6
7        // Verificar se o complemento já foi visto
8        if (seen.has(complement)) {
9            return [seen.get(complement)!, i];
10        }
11
12        // Armazenar o número atual e seu índice
13        seen.set(nums[i], i);
14    }
15
16    // Não deveria chegar aqui dado que há garantia de solução
17    return [];
18}

⏱️ Complexidade

Complexidade de Tempo: O(n)

• Percorremos o array uma única vez
• Cada operação de busca e inserção no hash map é O(1) em média
• Onde n é o tamanho do array

Complexidade de Espaço: O(n)

• No pior caso, armazenamos n-1 elementos no hash map
• Quando a solução está nos dois últimos elementos do array

🔗 Referências

• Two Sum - LeetCode
• Go Maps in Action
• TypeScript Map

📝 Notas Adicionais

Armadilhas Comuns

1. Usar o mesmo elemento duas vezes: O problema especifica que não podemos usar o mesmo índice duas vezes, mas podemos ter valores duplicados no array
2. Ordenar o array: Não ordene o array! Isso mudaria os índices originais
3. Retornar valores em vez de índices: O problema pede os índices, não os valores

Variações do Problema

• Two Sum II: Array já ordenado (permite usar two pointers)
• 3Sum: Encontrar três números que somam zero
• 4Sum: Encontrar quatro números que somam um target
• Two Sum - Input array is sorted: Permite otimização com two pointers sem hash map

Curiosidades

Este é um dos problemas mais populares do LeetCode e frequentemente aparece em entrevistas técnicas. É excelente para:

• Demonstrar conhecimento de hash maps
• Mostrar habilidade de otimização (de O(n²) para O(n))
• Praticar trade-off entre tempo e espaço