Two Sum
Você recebe um array de inteiros nums e um inteiro target. Exatamente dois elementos de nums, em duas posições diferentes, somam target. Retorne os índices desses dois elementos, com o índice menor primeiro.
Função
- numsinteger-array
- o array de inteiros a pesquisar
- targetinteger
- a soma das duas entradas deve atingir
- Retornainteger-array
- os dois índices, primeiro o menor
Restrições
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- Exatamente um par de posições diferentes soma
target.
Exemplos
- Entrada
- nums = [3, 8, 12, 5]target = 17
- Saída
- [2, 3]
- Explicação
- 12 está no índice 2 e 5 no índice 3, e 12 + 5 = 17. Nenhum outro par chega a 17.
- Entrada
- nums = [6, 1, 4, 10]target = 7
- Saída
- [0, 1]
- Explicação
- 6 no índice 0 e 1 no índice 1 somam 7: o par pode ser as duas primeiras entradas.
- Entrada
- nums = [2, -6, 9, 4, 13]target = 3
- Saída
- [1, 2]
- Explicação
- -6 no índice 1 e 9 no índice 2 somam 3. Os números negativos formam pares da mesma maneira que os positivos.
Para ir além
Se nums já chegasse ordenado, você conseguiria encontrar o par em O(n) de tempo usando apenas O(1) de memória extra?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Testar 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 número correspondente a 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 está faltando; 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 um número de formar um par consigo mesmo.
Solução
Verificar cada par funciona, mas o trabalho cresce com o quadrado do comprimento. Inverta a pergunta: estando em um número x, você já sabe que seu par deve ser target - x. Um mapa hash informa em tempo constante se você já passou por esse valor, então uma única passagem é suficiente.
Verifique cada par
Correta, mas não termina nos maiores testes
Intuição
Fixe um primeiro índice i e tente cada índice j à direita até que nums[i] + nums[j] seja igual a target. Começar j em i + 1 impede que uma posição forme par consigo mesma, testa cada par uma vez e coloca o índice menor primeiro. O par que você procura é um dos pares testados, então você o encontra.
n números formam cerca de n²/2 pares: n = 10^4 significa quase 5 × 10^7 adições.
Algoritmo
- Percorra com um loop
itodos os índices denums. - Para cada
i, percorra com um loopjdei + 1até o último índice. - Se
nums[i] + nums[j]for igual atarget, retorne[i, j]. - Se os dois loops terminarem, retorne um array vazio. O problema garante que isso nunca acontece.
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []Uma passagem com um mapa hash
Intuição
Para um nums[i] fixo, o loop interno da força bruta procura um valor que você já sabe de antemão: target - nums[i]. Essa varredura é, na verdade, uma busca disfarçada, e um mapa hash de valores para índices faz buscas em tempo constante, em média.
Busque primeiro, armazene depois. Assim, um número só pode formar um par com algo que veio antes dele, nunca consigo mesmo e, como o parceiro está sempre antes, seu índice vem primeiro. Cada número é visitado uma vez, com operações de tempo constante no mapa, então a busca é O(n); o custo é um mapa com até n entradas.
Algoritmo
- Crie um mapa vazio de valores para índices.
- Para cada índice
i, calculeneed, o valor que completa o par:targetmenosnums[i]. - Se
needestiver no mapa, retorne o índice armazenado seguido dei. - Caso contrário, armazene
nums[i]com o índiceie continue.
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
Armadilhas e casos extremos
- Armazenar um número antes de procurar seu complemento. Com
[4, 2, 6]etarget = 8, o 4 encontra a si mesmo e você retorna[0, 0]. - Retornar os índices na ordem errada. Ao procurar antes de armazenar, o índice do mapa é o menor e vem primeiro.
- Ordenar o array para usar dois ponteiros e, em seguida, retornar as posições na cópia ordenada. Mantenha o índice original de cada valor junto dele.
- Supor que os valores são positivos ou distintos.
[0, 7, -3, 0]comtarget = 0forma um par com os dois zeros:[0, 3]. - Em Lua e R, retornar os índices baseados em 1. Subtraia 1 de cada um.
Perguntas frequentes3
Qual é a complexidade de tempo do Two Sum?
A solução com tabela hash é executada em tempo O(n), porque visita cada número uma vez e cada busca ou inserção leva tempo constante, em média. Ela usa O(n) de espaço extra para a tabela. Verificar cada par leva tempo O(n²) e espaço O(1).
É possível resolver Two Sum sem espaço extra?
Não em tempo linear em um array não ordenado. Com espaço extra O(1), você volta a verificar cada par, o que é O(n²). O mapa hash troca O(n) de memória pelo tempo linear.
Como o Two Sum lida com números duplicados?
Duplicatas funcionam quando você procura o número correspondente antes de armazenar o número atual. Em [7, 3, 7] com target = 14, o primeiro 7 é armazenado no índice 0 e o segundo 7 o encontra, resultando em [0, 2]. Um 7 isolado nunca forma um par consigo mesmo: ele ainda não está no mapa quando você o procura.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def twoSum(nums, target):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
nums = [3, 8, 12, 5] target = 17
Saída Esperada
[2, 3]