Two Sum

Olá pessoa maravilhosa! ⭐
Eu sou o João, e ai, bão, meqctá?

Eu gostaria de compartilhar esse desafio de entrevista contigo, e te mostrar como eu resolveria ele, eu tive a ideia de compartilhar isso aqui com todos vocês pois quero incentivar todos nós a conseguirmos aquele emprego dos sonhos, como na Google, Meta, Microsoft, Aws e outras grandes empresas!

Então, bora resolver esse BO?
Primeiro, tente você mesmo!

Português

Dado um array de números inteiros e um número inteiro alvo, retorne os indices dos dois numeros que somados resultam no número alvo.

Assuma que cada array vai ter uma, e somente uma solução, e você não pode usar o mesmo número duas vezes.

Você deve retornar um array [0, 1] com os índices dos dois números, a ordem não importa.

Inglês

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Exemplos

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explicação: Porque nums[0] + nums[1] == 9, então, retornamos [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

Constantes

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Existe somente uma resposta certa.

Bora dar um trato nesse peão?

O maior desafio aqui é resolver isso com complexidade inferior a O(n2) se você não sabe o que significa esse "O" com o número ai, da uma olhadinha aqui obs o vídeo não é meu.

Primeiro, tente você mesmo!

Explicando a resposta

A resposta está no fim do post, para você não tomar spoiler sem querer!

1. Criamos um dicionário vazio chamado prevMap. Este dicionário será usado para armazenar os números e seus índices na lista.
2. Iniciamos um loop através da lista de números nums. Para cada número na lista, guardamos o seu índice e o valor na variável index e num, respectivamente.
3. Calculamos a diferença entre o valor alvo e o número atual. Essa diferença será usada para verificar se já existe um número na lista que, quando somado com o número atual, resulta no valor alvo.
4. Verificamos se a diferença está no dicionário prevMap. Se sim, significa que encontramos dois números que, quando somados, resultam no valor alvo. Retornamos então um array com os índices desses dois números.
5. Se a diferença não estiver no dicionário, adicionamos o número atual e seu índice ao dicionário prevMap.
6. Continuamos o loop até percorrer toda a lista.
7. Se o loop terminar sem encontrar dois números que, quando somados, resultam no valor alvo, retornamos um valor vazio.

def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {} 
        
        for index, num in enumerate(nums):
            diff = target - num
            if diff in prevMap:
                return [prevMap[diff], index]
            prevMap[num] = index
        return

CURTIU? ❤️ DA SEU UP 🆙!

Explicação de como criamos esse algorítimo

1. Bem, a primeira coisa que faremos é criar um prevMap = {} , um dict, o motivo de usar isso é por que no Python dicts por debaixo dos panos são Hash Maps, o que nós permite fazer operações de Busca e Inserção com complexidade O(1).

(Também seria possível usar set(), alterando um pouco o código)

2. Agora, vamos iniciar o nosso loop for index, num in enumerate(nums):, usamos enumerate para pegar os indexes dos números na list (array).

3. Primeiro, vamos pegar a diferença entre o alvo e o número atual, ou seja, se temos uma lista [2,7,11,15] e o alvo é 9, ao entrar no primeiro elemento 9 - 2 é 7, mas por que fazemos isso? Pense comigo, quando fazemos isso nós estamos calculando quanto falta, pra somado desse elemento 2 chegue em 9, nesse caso, falta 7, como nós queremos dois números que somados chegam ao alvo, se salvarmos quanto cada elemento falta para chegar no alvo, ao passar por um que somado a esse chega ao alvo, nós obtemos nossa resposta, não entendeu? Acompanha comigo (no fim vou fazer um passo a passo).

4. Depois de calcular a diferença, nós entramos no if diff in prevMap:, ele vai procurar essa diferença no prevMap ou seja, imagine que estamos no primeiro elemento do array, 2, a diferença de 9 - 2 é 7, ele está perguntando se em prevMap tem 7, não tem, então o que ele faz? Ele vai prevMap[num] = index, adicionar na posição do nosso número, no caso 2, o index do número 2 na nossa list (array). Acompanha comigo.

5. Se ele tivesse achado o 7 na lista, ele ia ter retornado return [prevMap[diff], index].

Vamos passo a passo no array imaginando que somos o algorítimo

Como passamos por 2 e a diferença deu 7, procuramos em prevMap mas não achamos 7, nós vamos adicionar 2 em prevMap.

O próximo número é ([2,7,11,15]), nesse caso 7, calculamos a diferença do alvo 9, menos o atual, ou seja 9 - 7, que é? 2, então vamos no dict prevMap e procuramos por 2, e olha só, 2 existe ele era o elemento passado, então, nós achamos a resposta! Vamos retornar um array com as posições dos dois, no caso, a primeira posição prevMap[diff] que resulta em 0, que é a posição de 2 no list inicial, lembra que salvamos na posição do número o valor do index dele? E a segunda posição o proprio index do elemento atual sendo iterado, 7, e a resposta é [0,1].

Mas e se não fosse 9 o alvo? E se no list ([2,7,11,15]) o alvo fosse 13? Bem, é só seguir a nossa lógica, iamos chegar no 7, calcular a diferença, ia dar 13 - 7 = 6, a gente ia procurar 6, não ia achar, então iamos pular pro próximo e tudo ia começar de novo.

Chegariamos no 11, calculamos a diferença, ia dar 13 - 11 = 2, procuramos 2 em prevMap e lá estaria ele, a primeira posição do nosso array, lembra dele? Poisé, agora você sabe como o algorítimo funciona :)