Two Sum — Encontrando Dois Números que Somam um Valor

O Two Sum é um dos problemas mais conhecidos do LeetCode.

Ele é um problema simples de entender, mas muito importante para aprender conceitos fundamentais de algoritmos e estruturas de dados.

O problema ajuda a entender:

• Arrays
• Loops
• Hash Maps
• Complexidade de algoritmos
• Otimização de código

A pergunta é:

Dado um array de números e um valor alvo, encontre dois números cuja soma seja igual ao valor alvo.

1. O problema

Imagine que temos:

numbers = [2, 7, 11, 15]

target = 9

Precisamos encontrar dois números que somados resultem em 9.

Podemos observar:

2 + 7 = 9

Portanto, a resposta é:

[0, 1]

Porque:

numbers[0] = 2
numbers[1] = 7

O resultado esperado são os índices dos números, e não os números em si.

2. Outro exemplo

Imagine:

numbers = [3, 2, 4]

target = 6

Precisamos encontrar:

2 + 4 = 6

Os índices são:

2 → índice 1

4 → índice 2

Portanto:

[1, 2]

3. A solução mais simples

Uma primeira solução seria comparar todos os números entre si.

Por exemplo:

function twoSum(numbers: number[], target: number): number[] {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) {
        return [i, j];
      }
    }
  }

  return [];
}

Podemos testar:

const result = twoSum([2, 7, 11, 15], 9);

console.log(result);

Resultado:

[0, 1]

4. Como essa solução funciona?

Temos dois loops.

O primeiro seleciona um número:

2

O segundo compara com os próximos:

2 + 7 = 9

Encontramos a resposta.

Se não encontrar:

2 + 11
2 + 15

Passamos para o próximo:

7 + 11
7 + 15

E assim por diante.

O problema é que precisamos testar muitas combinações.

5. Complexidade

Para um array com n elementos, podemos acabar fazendo aproximadamente:

n × n

comparações.

Portanto:

Time Complexity: O(n²)

Por exemplo:

10 elementos
→ aproximadamente 100 comparações

1.000 elementos
→ aproximadamente 1.000.000 comparações

1.000.000 elementos
→ aproximadamente 1.000.000.000.000 comparações

Isso pode ficar muito lento.

Precisamos encontrar uma solução melhor.

6. A ideia do HashMap

A pergunta principal é:

Se eu tenho um número, qual número preciso encontrar para chegar ao target?

Imagine:

number = 2

target = 9

Precisamos de:

9 - 2 = 7

Ou seja:

2 + 7 = 9

Então, para cada número, calculamos:

complement = target - number

Depois verificamos se esse complemento já apareceu.

7. Usando um HashMap

Em JavaScript e TypeScript, podemos usar um Map.

A ideia é armazenar:

número → índice

Por exemplo:

2 → 0
7 → 1
11 → 2
15 → 3

Assim conseguimos verificar rapidamente se um número já foi encontrado.

8. Solução otimizada

function twoSum(numbers: number[], target: number): number[] {
  const map = new Map<number, number>();

  for (let i = 0; i < numbers.length; i++) {
    const current = numbers[i];
    const complement = target - current;

    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }

    map.set(current, i);
  }

  return [];
}

Vamos entender passo a passo.

9. Primeiro elemento

Temos:

numbers = [2, 7, 11, 15]

target = 9

Começamos com:

Map = {}

Primeiro número:

current = 2

Calculamos:

complement = 9 - 2

Resultado:

complement = 7

Perguntamos:

O número 7 já apareceu?

Ainda não.

Então armazenamos:

Map

2 → 0

10. Segundo elemento

Agora:

current = 7

Calculamos:

complement = 9 - 7

Resultado:

complement = 2

Perguntamos:

O número 2 já apareceu?

Sim.

Temos:

2 → índice 0

E estamos no:

7 → índice 1

Então retornamos:

[0, 1]

Resultado:

2 + 7 = 9

11. Visualizando o algoritmo

Podemos pensar assim:

Array:

[2, 7, 11, 15]

Primeiro:

2
│
├── Target = 9
│
└── Preciso de 7

O 7 ainda não existe no Map.

Então:

Map

2 → 0

Agora:

7
│
├── Target = 9
│
└── Preciso de 2

O 2 existe:

2 → 0

Encontramos:

[0, 1]

12. Complexidade otimizada

A solução com Map percorre o array apenas uma vez.

Portanto:

Time Complexity: O(n)

O Map utiliza memória adicional:

Space Complexity: O(n)

Temos então:

Solução simples:

Tempo: O(n²)
Memória: O(1)


Solução com HashMap:

Tempo: O(n)
Memória: O(n)

Trocamos memória por velocidade.

Esse é um dos trade-offs mais comuns em algoritmos.

13. Um exemplo prático: sistema de pagamentos

Imagine que você está desenvolvendo um sistema de pagamentos.

Você possui uma lista de valores disponíveis:

[10, 20, 50, 100, 200]

E precisa encontrar duas transações que juntas formem um determinado valor.

Por exemplo:

target = 70

Podemos encontrar:

20 + 50 = 70

Usando:

const transactions = [10, 20, 50, 100, 200];

const result = twoSum(transactions, 70);

console.log(result);

Resultado:

[1, 2]

Porque:

transactions[1] = 20
transactions[2] = 50

Então:

20 + 50 = 70

14. Um exemplo ainda mais realista

Imagine um sistema de e-commerce que precisa encontrar dois produtos cujo preço combinado seja exatamente o valor de um cupom.

Temos:

const products = [
  29.90,
  49.90,
  79.90,
  99.90,
  149.90
];

const couponValue = 129.80;

Precisamos encontrar dois produtos:

29.90 + 99.90 = 129.80

Uma implementação poderia ser:

function findProductsForCoupon(
  prices: number[],
  couponValue: number
): number[] {
  const map = new Map<number, number>();

  for (let i = 0; i < prices.length; i++) {
    const price = prices[i];
    const needed = couponValue - price;

    if (map.has(needed)) {
      return [map.get(needed)!, i];
    }

    map.set(price, i);
  }

  return [];
}

Uso:

const products = [
  29.90,
  49.90,
  79.90,
  99.90,
  149.90
];

const result = findProductsForCoupon(
  products,
  129.80
);

console.log(result);

Resultado:

[0, 3]

Ou seja:

Produto 0 → R$ 29,90

Produto 3 → R$ 99,90

Total:

R$ 29,90 + R$ 99,90 = R$ 129,80

Em um sistema real, provavelmente usaríamos valores inteiros em centavos para evitar problemas de precisão com números decimais:

const productsInCents = [
  2990,
  4990,
  7990,
  9990,
  14990
];

const couponValue = 12980;

Agora:

2990 + 9990 = 12980

Isso evita problemas comuns de ponto flutuante.

15. O conceito por trás do Two Sum

O mais importante nesse problema não é apenas encontrar dois números.

É aprender a fazer a pergunta:

"O que eu preciso encontrar para completar o valor que tenho?"

Se:

target = 10

E encontramos:

current = 3

Então:

needed = 10 - 3

Precisamos encontrar:

7

Se encontramos:

current = 8

Precisamos de:

2

A lógica é:

             TARGET
                │
                ▼
        TARGET - CURRENT
                │
                ▼
            NEEDED

Depois verificamos se NEEDED já foi encontrado.

16. E se existirem números negativos?

A solução continua funcionando.

Por exemplo:

numbers = [-3, 4, 7, 2]

target = 1

Temos:

-3 + 4 = 1

A solução encontra:

[-3, 4]

Porque:

1 - (-3) = 4

O Map não se importa se os valores são:

• Positivos
• Negativos
• Zero

17. E se o número aparecer duas vezes?

Por exemplo:

numbers = [3, 3]

target = 6

Precisamos de:

3 + 3 = 6

O algoritmo funciona:

Primeiro 3
    │
    ▼
Map = { 3 → 0 }

Segundo 3
    │
    ▼
Preciso de 3
    │
    ▼
3 já existe

Resultado:

[0, 1]

18. O padrão "Complement"

O padrão utilizado no Two Sum é extremamente importante.

Podemos resumir:

for each item:

    needed = target - current

    if needed exists:
        found

    else:
        store current

Esse padrão aparece em muitos problemas envolvendo:

• Soma
• Diferença
• Frequência
• Busca de pares
• Duplicatas

E normalmente envolve:

HashMap

ou:

HashSet

19. Two Sum vs força bruta

A diferença principal:

Força Bruta

Para cada número
    Para cada outro número
        Testar combinação

Complexidade:

O(n²)

HashMap

Para cada número
    Calcular complemento
    Procurar no Map

Complexidade:

O(n)

A grande mudança foi deixar de procurar:

"Qualquer par possível?"

e passar a perguntar:

"Qual número exatamente eu preciso?"

Essa mudança de pensamento é uma das principais lições do problema.

Conclusão

O Two Sum consiste em encontrar dois números dentro de um array cuja soma seja igual a um valor alvo.

Por exemplo:

numbers = [2, 7, 11, 15]

target = 9

A resposta é:

2 + 7 = 9

E os índices:

[0, 1]

A solução mais simples utiliza dois loops:

O(n²)

Mas podemos otimizar utilizando um Map:

O(n)

A ideia central é calcular o complemento:

needed = target - current

E verificar se ele já foi encontrado.

A solução final fica:

function twoSum(numbers: number[], target: number): number[] {
  const map = new Map<number, number>();

  for (let i = 0; i < numbers.length; i++) {
    const needed = target - numbers[i];

    if (map.has(needed)) {
      return [map.get(needed)!, i];
    }

    map.set(numbers[i], i);
  }

  return [];
}

A grande lição do Two Sum é:

Quando você precisa encontrar dois valores que juntos satisfazem uma condição, pense no complemento que falta e use uma estrutura de dados eficiente para encontrá-lo rapidamente.

Esse padrão de pensamento é muito mais importante do que o próprio problema e aparece frequentemente em entrevistas técnicas e em outros problemas de algoritmos.