Leetcode: duas somas e uma abordagem intuitiva

Imagine-se como o orgulhoso proprietário de uma loja de souvenirs dentro do Spot-On Change Hotel. Ao fechar a caixa registadora, nota-se um excesso de 8 euros. Parece que um hóspede não recebeu o troco exato. Isso poderia manchar a reputação do hotel. Para evitar isso, você decide resolver o mistério da alteração incorreta. Ao abrir o caixa da loja, você descobre que o erro ocorreu em duas contas diferentes!

Você traça um plano: visitar cada quarto e perguntar aos hóspedes que troco eles receberam na loja até encontrar os dois com a conta errada. Chegando ao primeiro andar, um hóspede relata ter recebido 4 euros de troco. Você calcula que precisa encontrar um número que, somado aos 4 euros, resulte em 8. Passando para o segundo andar, o troco do hóspede é de 5 euros. 4 + 5 resulta em 9, então não pode ser esse… Quinto andar, sexto… Décimo, NÃO, NÃO, NÃO!

Como não encontrou o valor na primeira tentativa, você desce até o segundo andar e começa a perguntar novamente a todos os convidados sobre o troco deles para poder comparar com o valor do próximo andar inicial, cansativo, não é isto? Na ciência da computação, esse método de busca é chamado de força bruta, um método de busca extremamente lento que funciona comparando um item com os seguintes no array.

Isso consome muito tempo e não é eficiente, imagine subir e descer todos os andares do Spot-On Change Hotel diversas vezes! Isso não é prático para você e também não é prático para o computador.

Se você está curioso para saber como seria subir e descer andares em um programa de software, ficaria assim em JavaScript:

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

Depois de avaliar a situação com calma, você percebe que existe uma maneira mais eficiente de encontrar os dois convidados com o troco errado.

Você refina sua intuição matemática inicial de que 9 euros são iguais a x + y. Aplicando um pouco de aritmética, você percebe que: x + y = 9 é o mesmo que dizer que y = 9 — x, e isso faz toda a diferença na hora de aumentar a eficiência da sua busca.

Outra coisa que mudou na sua estratégia é que agora você vai levar um bloco de notas para anotar os valores que os hóspedes te informarem, assim você não precisa pedir o mesmo valor duas vezes para os convidados, e não precisa gastar o dia subindo e descendo escadas. (Que momento terrível para o elevador quebrar!).

Com as novas ferramentas em mãos, dirige-se ao primeiro andar, onde um hóspede informa que tem 5 euros de troco. Você registra isso como {5: 0}, indicando um valor de 5 na posição 0. Substituindo x por 5 na equação, você calcula y = 8–5, resultando em y = 3. Como seu bloco de notas ainda está vazio, você não você não tem o número 3 registrado, que seria o número complementar ao 5 para chegar ao resultado 8. Você então anota o número 5 no seu bloco de notas (lembre-se de sempre anotar o número verificado no momento e não o seu complemento; você usará apenas o complemento para compará-lo com o número alvo que você anotou). Você segue para o segundo hóspede, que menciona receber 2 euros de troco. Aplicando a fórmula novamente: y = 8–2 => y = 6, você verifica seu registro, onde não encontra nenhum número 6. Assim, você adiciona 2 ao seu registro, que agora fica como {5: 0, 2: 1}. Continuando a busca, o próximo hóspede informa ter recebido 3 euros de troco. Você calcula novamente: y = 8–3 => y = 5. Bingo! Você tem um 5 registrado no seu bloco de notas! O hóspede do piso 0 é complementar ao do piso 2! Essa abordagem é conhecida como tabela hash e é muito mais rápida e eficiente, tanto para você quanto para o computador. Em JavaScript, isso seria implementado da seguinte forma:

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

Este é um problema fácil do Leetcode que só se torna fácil depois de você entender os conceitos por trás dele. Recomendo que você tente resolver o problema sozinho e gaste algum tempo tentando construir uma intuição por trás dele, crie sua própria analogia, revise e tente escrever pseudocódigo antes de passar para a solução.

Espero que minha analogia tenha ajudado você a entender melhor os conceitos por trás do desafio das duas somas.

Vejo você na próxima vez!