Two Sums - Hacker Rank

📝 Descrição

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

Exemplo 1

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Exemplo 2

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

Output: [1,2]

✅ Casos de teste

Caso 1

Entrada

Input: nums = [2,7,11,15], target = 9

Saída

Output: [0,1]

🚀 Como resolvi?

Temos algumas formas de resolver esse tipo de questão. A primeira delas que vem à mente é:

1. Fixar um ponteiro no número atual
2. Fixar um ponteiro no próximo número
3. Percorrer todos os números após o número atual, somando-os ao número atual e verificando se o resultado é igual ao target.

O problema dessa solução é a complexidade dela. Por termos dois laços aninhados, a abordagem tem complexidade $O(n^2)$. E se armazenássemos os números já vistos e trabalhássemos procurando o seu complemento neles?

1. Criaremos um Hash para armazenar o número e a posição dele.
2. Ao passo que vamos percorrendo o vetor, verificamos se o complemento $complemento=target-atual$ está no mapa.
3. Caso esteja, adicionamos a posição do complemento e a posição do atual na resposta e quebramos o laço.
4. Adicionamos o número atual e sua posição no nosso mapa.

🛠️ Implementação

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        complements = {}
        result = []
        for i in range(len(nums)):
            complement = target - nums[i]
            if complements.get(complement) is not None:
                result = [complements[complement], i]
                break
            complements[nums[i]] = i
        return result

🧠 O que aprendemos?

Podemos utilizar mapas para realizar buscas eficientes. Isso só acontece pois a busca ocorre em $O(1)$ caso não haja colisão. Porém, como troca, acabamos aumentando um pouco do consumo da memória.