Duas somas

Solução 1 — Força bruta O(n²)

Dois loops aninhados, compara cada par possível.

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

  return null
}

Funciona. Mas para n números, o loop interno roda n vezes para cada iteração do externo. O trabalho cresce com o quadrado — lento demais para entradas grandes.

Solução 2 — Mapa hash em O(n)

Passo 5 — Guardar o que já foi visto

A ideia é: ao invés de buscar o complemento no array, guarde os números que você já viu em uma estrutura separada.

Essa estrutura precisa responder em tempo constante: “esse número existe? E em qual posição ele estava?”

Em JavaScript, Map faz exatamente isso. Você guarda valor → índice:

const seen = new Map<number, number>()

seen.set(2, 0)   // número 2 estava na posição 0
seen.has(2)      // true — busca instantânea
seen.get(2)      // 0 — posição do número 2

Passo 6 — Montar a solução final

Com Map, você percorre o array uma única vez:

1. Calcula o complemento: target - nums[i]
2. Verifica se o complemento já está no Map
3. Se estiver, você encontrou o par — retorna os dois índices
4. Se não estiver, guarda o número atual no Map com sua posição

Um detalhe importante: cheque o complemento antes de guardar o número atual. Isso evita usar o mesmo elemento duas vezes.

export function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>()

  for (let index = 0; index < nums.length; index += 1) {
    const value = nums[index]
    const complement = target - value

    if (seen.has(complement)) {
      return [seen.get(complement)!, index]
    }

    seen.set(value, index)
  }

  return null
}

Uma passada pelo array. Busca O(1) por complemento. Resultado: O(n) no total.

O que dizer na entrevista

Uma explicação curta e boa seria:

A versão inicial compara todos os pares e custa O(n²). Como eu só preciso saber se o complemento já apareceu, uso mapa hash para busca em O(1) e resolvo em uma passada.

Isso mostra tres coisas:

• você entendeu a versão inicial e sabe nomear o custo dela
• você justificou a otimização com uma razão concreta
• você conectou a estrutura de dados a necessidade real

Quando esse padrão aparece de novo

A mesma ideia volta quando o problema pede:

• lembrar do que já apareceu
• detectar repetição
• descobrir se um complemento existe
• agrupar ou consultar rápido durante a iteração

O ponto não e decorar mapa hash.

O ponto e perceber quando o problema pede memória durante a passada — e escolher a estrutura certa para isso.