paint-brush
Leetcode: duas somas e uma abordagem intuitiva por@carolisabino
797 leituras
797 leituras

Leetcode: duas somas e uma abordagem intuitiva

por Caroline Sabino
Caroline Sabino HackerNoon profile picture

Caroline Sabino

@carolisabino

Software engineer.

4 min read2024/04/23
Read on Terminal Reader
Read this story in a terminal
Print this story

Muito longo; Para ler

Construir a intuição por trás da solução de problemas para que você possa aplicá-los aos seus próprios cenários de caso.
featured image - Leetcode: duas somas e uma abordagem intuitiva
Caroline Sabino HackerNoon profile picture
Caroline Sabino

Caroline Sabino

@carolisabino

Software engineer.

0-item
1-item

STORY’S CREDIBILITY

Code License

Code License

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Guide

Guide

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.


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.


imagem de entrevistating.io

imagem de entrevistating.io




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!

L O A D I N G
. . . comments & more!

About Author

Caroline Sabino HackerNoon profile picture
Caroline Sabino@carolisabino
Software engineer.

Rótulos

ESTE ARTIGO FOI APRESENTADO EM...

Read on Terminal Reader
Read this story in a terminal
 Terminal
Read this story w/o Javascript
Read this story w/o Javascript
 Lite
X REMOVE AD