Two Sum II: Sorted Input
Você recebe um array de números inteiros numbers ordenado em ordem não decrescente e um número inteiro target. Exatamente um par de posições diferentes contém dois valores cuja soma é igual a target. Retorne essas duas posições como índices baseados em 0, com o menor índice primeiro.
Função
- numbersinteger-array
- o array ordenado de inteiros
- targetinteger
- a soma que os dois valores devem alcançar
- Retornainteger-array
- os dois índices baseados em 0 [i, j] com i < j e numbers[i] + numbers[j] == target
Restrições
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbersestá ordenado em ordem não decrescente.- Exatamente um par de índices
i < jtemnumbers[i] + numbers[j] == target.
Exemplos
- Entrada
- numbers = [-4, 1, 3, 8, 12]target = 9
- Saída
- [1, 3]
- Explicação
- 1 está no índice 1 e 8 no índice 3, e 1 + 8 = 9. Nenhum outro par chega a 9: por exemplo, -4 + 12 = 8.
- Entrada
- numbers = [2, 2, 5, 7]target = 4
- Saída
- [0, 1]
- Explicação
- Os dois 2 nos índices 0 e 1 são duas posições diferentes, então podem formar o par: 2 + 2 = 4.
- Entrada
- numbers = [-10, -3, 0, 6]target = -4
- Saída
- [0, 3]
- Explicação
- -10 no índice 0 e 6 no índice 3 resultam em -10 + 6 = -4. A resposta pode abranger todo o array.
+13 testes ocultos ao enviar
Para ir além
Você consegue resolvê-lo em O(n) tempo usando O(1) de memória extra?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
O array está ordenado. Observe juntos o menor e o maior valor. O que a soma deles indica quando é menor que
target?Se o primeiro valor mais o último valor for muito pequeno, o primeiro valor será muito pequeno para todos os pares, pois o último valor já é o maior. Você pode descartá-lo.
Mantenha um ponteiro em cada extremidade. Quando a soma for muito pequena, mova o ponteiro esquerdo para a direita; quando for muito grande, mova o ponteiro direito para a esquerda. Pare quando a soma for igual a
target.
Solução
Um mapa de hash resolve a versão não ordenada em uma única passagem, mas custa O(n) de memória. Aqui, o array está ordenado, e essa ordem indica para que lado você deve mover os ponteiros. Coloque um ponteiro em cada extremidade. Se a soma for muito pequena, somente um valor maior à esquerda pode ajudar; se for muito grande, somente um valor menor à direita pode ajudar. A cada etapa, um valor é descartado de vez, então uma única passagem encontra o par sem memória extra.
Verifique cada par
Correta, mas não termina nos maiores testes
Intuição
Teste cada par de posições i < j e verifique se numbers[i] + numbers[j] é igual a target. Como i percorre a lista da esquerda para a direita e j começa logo depois dele, o primeiro par encontrado já tem o índice menor primeiro.
Isso está correto, mas ignora a ordem crescente. Com n = 10^4, há cerca de 5 × 10^7 pares e, quando a resposta está perto do fim do array, você testa quase todos eles. Isso é lento demais para os testes grandes.
Algoritmo
- Percorra cada índice com
i. - Percorra
jdei+1até o último índice. - Se
numbers[i] + numbers[j]for igual atarget, retorne[i, j].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []Busca binária para cada parceiro
Intuição
Depois de fixar o primeiro valor numbers[i], você sabe exatamente qual é seu par: target - numbers[i]. A parte do array à direita de i está ordenada, então a busca binária pode dizer em O(log n) etapas se esse par está lá.
Para [-4, 1, 3, 8, 12] e target = 9: em i = 0, o par seria 13, que não está presente. Em i = 1, o par é 8, e a busca o encontra no índice 3. A resposta é [1, 3].
Buscar apenas à direita de i mantém o índice menor primeiro e impede que um valor forme par consigo mesmo. O par é único, então o valor correspondente aparece no máximo uma vez nesse intervalo, e qualquer ocorrência é a resposta. No total: n buscas de O(log n) cada.
Algoritmo
- Percorra em loop
ide 0 an-2. - Calcule
need = target - numbers[i]. - Faça uma busca binária por
neednos índices dei+1an-1. - Se encontrá-lo em
mid, retorne[i, mid].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []Dois ponteiros a partir das duas extremidades
Intuição
Comece com left = 0 e right = n-1 e observe numbers[left] + numbers[right]. Se for igual a target, você terminou. Se for muito pequeno, numbers[left] não pode fazer parte da resposta: mesmo combinado com o maior valor ainda em jogo, ele fica abaixo do necessário. Então mova left para a direita. Se a soma for muito grande, numbers[right] também não pode fazer parte dela, pois até mesmo o menor valor restante para combinar ultrapassa o alvo. Então mova right para a esquerda.
Cada movimento descarta um valor que nunca poderá fazer parte do par, e o próprio par nunca é descartado. Os ponteiros se encontram após, no máximo, n-1 movimentos, então a varredura é O(n) e usa duas variáveis.
Em [-4, 1, 3, 8, 12] com target = 9: -4 + 12 = 8 é muito pequeno, então left avança para o índice 1. Em seguida, 1 + 12 = 13 é muito grande, então right recua para o índice 3. Agora, 1 + 8 = 9, e a resposta é [1, 3].
Algoritmo
- Defina
leftcomo 0 erightcomon-1. - Enquanto
left < right, calculetotal = numbers[left] + numbers[right]. - Se
totalfor igual atarget, retorne[left, right]. - Se
totalfor menor, some 1 aleft; se for maior, subtraia 1 deright.
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
Armadilhas e casos extremos
O loop de dois ponteiros é curto, então os bugs ficam escondidos nos detalhes ao redor dele.
- Retornar posições começando em 1. Esta versão espera índices começando em 0: para
[-4, 1, 3, 8, 12]etarget = 9, a resposta é[1, 3], não[2, 4]. Em Lua e R, subtraia 1 antes de retornar. - Usar
left <= rightno loop. Quando os ponteiros se encontram, a soma usaria o mesmo valor duas vezes. - Mover o ponteiro errado. Uma soma pequena demais precisa de um valor maior, e só
leftpode fornecer um. - Rejeitar valores duplicados.
[2, 2, 5, 7]comtarget = 4usa os dois valores 2, que estão em posições diferentes. - Estouro. Os limites aqui mantêm todas as somas dentro de um inteiro de 32 bits. Se os valores pudessem chegar a
10^9, some-os usando um tipo de 64 bits.
Perguntas frequentes4
Por que dois ponteiros funcionam para Two Sum em um array ordenado?
Quando a soma das duas extremidades é pequena demais, o valor da esquerda é pequeno demais para todos os parceiros que ainda estão em jogo, porque a extremidade direita é a maior entre eles. Você pode descartá-lo de vez. O mesmo argumento permite descartar o valor da direita quando a soma é grande demais. O par que corresponde à resposta nunca é descartado, então os ponteiros terminam nele.
Qual é a complexidade de tempo do Two Sum II?
A solução com dois ponteiros é executada em O(n) e usa O(1) de espaço extra: a cada etapa, um ponteiro avança para dentro, e eles se encontram após no máximo n-1 etapas. Fazer uma busca binária para cada parceiro leva O(n log n), e verificar todos os pares leva O(n²).
Por que não usar um mapa hash, como no primeiro Two Sum?
Um mapa hash funciona e também é executado em tempo O(n), mas armazena até n valores. A ordem ordenada torna essa memória desnecessária: os dois ponteiros sabem para que lado avançar apenas pela soma. Entrevistadores perguntam essa versão para ver se você usa a ordem que recebeu.
Quando a busca binária é a melhor opção aqui?
Quando um valor é fixo e você só precisa encontrar o outro elemento do par. Se numbers[0] precisa fazer parte do par, uma busca binária encontra o outro índice em O(log n). Para encontrar um par desconhecido, a varredura com dois ponteiros é mais rápida do que n buscas separadas.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def twoSumSorted(numbers, target):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
numbers = [-4, 1, 3, 8, 12] target = 9
Esperado
[1, 3]