Two Sum
Você recebe uma lista de números inteiros e um valor-alvo. Exatamente dois números da lista somam o valor-alvo, e sua tarefa é informar em quais posições eles estão.
Considere nums = [3, 8, 12, 5] e target = 17. O valor 12 está no índice 2 e 5 está no índice 3, e 12 + 5 = 17, então a resposta é [2, 3].
Os dois números devem vir de posições diferentes. Em [4, 2, 6] com target = 8, não é permitido usar o 4 duas vezes; a resposta é [1, 2] porque 2 + 6 = 8. Porém, o mesmo valor pode aparecer duas vezes: em [7, 3, 7] com target = 14, a resposta é [0, 2].
Escreva uma função chamada twoSum que recebe um array de números inteiros nums e um número inteiro target, e retorna um array com dois índices [i, j] tais que nums[i] + nums[j] seja igual a target.
Os índices devem corresponder a duas posições diferentes e ser retornados em ordem crescente (i menor que j). Toda entrada tem exatamente um par assim.
Restrições: 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Função
- arg1integer-array
- arg2integer
- Retornainteger-array
Exemplos
- Entrada
- arg1 = [3, 8, 12, 5]arg2 = 17
- Saída
- [2, 3]
- Entrada
- arg1 = [6, 1, 4, 10]arg2 = 7
- Saída
- [0, 1]
- Entrada
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Saída
- [1, 2]
+13 testes ocultos ao enviar
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Tentar cada par com dois loops aninhados está correto, mas, com 10.000 números, isso representa cerca de 50 milhões de verificações. Você consegue encontrar o par de cada número sem percorrer a lista novamente?
Quando você está diante de um valor
x, já sabe qual valor completaria o par: o alvo menosx. A única questão é se você já passou por esse valor antes e em qual índice.Percorra a lista uma vez e mantenha um mapa hash de cada valor pelo qual você passou até seu índice. Em cada posição, procure primeiro o complemento que falta; se ele estiver no mapa, você terá os dois índices. Caso contrário, armazene o valor atual e continue. Procurar antes de armazenar é o que impede que um número forme um par consigo mesmo.
Em breve, uma explicação completa deste problema.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def twoSum(nums, target):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
arg1 = [3, 8, 12, 5] arg2 = 17
Esperado
[2, 3]