Find Pivot Index

Q: Qual é a complexidade de tempo de Find Pivot Index?

A solução usando o total e a soma acumulada leva O(n) tempo: uma passagem para somar o array e outra para percorrê-lo. Ela usa O(1) de espaço extra. Recalcular os dois lados em cada índice leva O(n²) tempo.

FácilSoma de prefixos

+10

Você recebe um array de números inteiros nums. Um índice pivô é um índice em que a soma dos valores à sua esquerda é igual à soma dos valores à sua direita. O valor no próprio pivô não pertence a nenhum dos lados, e um lado sem valores tem soma igual a 0.

Retorne o índice pivô mais à esquerda ou -1 se nenhum índice for um pivô.

Função

pivotIndex(nums: integer-array) → integer

numsinteger-array: o array de inteiros a ser balanceado
Retornainteger: o índice do pivô mais à esquerda, ou -1 quando não houver nenhum

Restrições

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Exemplos

Entrada: nums = [3, 1, 5, 2, 2]
Saída: 2
Explicação: No índice 2, o lado esquerdo é 3 + 1 = 4 e o lado direito é 2 + 2 = 4. Os índices 0 e 1 não estão em equilíbrio (lado esquerdo 0 contra 10, lado esquerdo 3 contra 9), então 2 é o pivô mais à esquerda.

Entrada: nums = [1, 2, 3]
Saída: -1
Explicação: Os três candidatos dão 0 contra 5, 1 contra 3 e 3 contra 0. Nenhum índice se equilibra, então a resposta é -1.

+17 testes ocultos ao enviar

Para ir além

Você consegue encontrar o pivô mais à esquerda lendo cada valor apenas uma vez, sem somar o total primeiro? Quanto isso custa em memória?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Verificar um índice envolve duas somas, mas recalculá-las em cada índice faz o trabalho crescer com o quadrado do comprimento. A solução é parar de recalcular: a soma à esquerda cresce com um valor a cada etapa, e a soma à direita é o que resta do total. Uma passagem para calcular o total e uma segunda passagem com uma soma acumulada à esquerda encontram o pivô mais à esquerda, usando dois números na memória.

Some os dois lados em cada índice

Correta, mas não termina nos maiores testes

Intuição

Siga a definição. Para cada índice i, some os valores anteriores a ele, some os valores posteriores a ele e compare. O primeiro índice em que as duas somas coincidem é a resposta, porque você testa os índices da esquerda para a direita.

As extremidades se resolvem sozinhas. No índice 0, o loop da esquerda é executado zero vezes, então a soma à esquerda é 0; no último índice, o loop da direita é executado zero vezes. É por isso que [4, -4, 9] retorna 2.

O custo é o problema. Para cada índice, são somados os outros n-1 valores, então o trabalho total é de cerca de n² adições. Com 10.000 valores, isso chega perto de 100 milhões de adições, e a maioria repete somas que você já calculou um índice antes.

Algoritmo

Percorra todos os índices de nums usando i.

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left = 0
        for j in range(i):
            left += nums[j]
        right = 0
        for j in range(i + 1, n):
            right += nums[j]
        if left == right:
            return i
    return -1

Soma prefixada

Intuição

A força bruta continua somando trechos do array. Um array de soma de prefixos faz esse trabalho uma única vez. Seja prefix[k] a soma dos primeiros k valores, com prefix[0] = 0. Para [3, 1, 5, 2, 2], isso resulta em [0, 3, 4, 9, 11, 13].

Agora, qualquer trecho é a diferença entre duas entradas. O lado esquerdo do índice i corresponde aos primeiros i valores, então é prefix[i]. O lado direito corresponde a tudo após nums[i], que é prefix[n] - prefix[i+1]. No índice 2, isso resulta em 4 à esquerda e 13 - 9 = 4 à direita: um pivô.

Construir o array exige uma passagem, e cada verificação leva tempo constante, então a busca inteira é O(n). O custo é n+1 números extras na memória.

Algoritmo

Crie prefix com comprimento n+1 e prefix[0] = 0.
Preencha-o: prefix[k+1] = prefix[k] + nums[k].
Para cada índice i, leia a soma à esquerda como prefix[i] e a soma à direita como prefix[n] - prefix[i+1].
Retorne o primeiro i em que elas são iguais ou -1 após o loop.

def pivotIndex(nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values.
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + nums[k]
    for i in range(n):
        left = prefix[i]
        right = prefix[n] - prefix[i + 1]
        if left == right:
            return i
    return -1

Soma total e soma acumulada à esquerda

Intuição

Observe quais entradas do prefixo a abordagem anterior lê. No índice i, ela precisa de prefix[i], prefix[i+1] e prefix[n]. O último é o total, que nunca muda, e os outros dois são a soma acumulada que você teria ao percorrer o array uma vez. Portanto, você pode manter o total e uma única soma acumulada à esquerda, em vez do array inteiro.

Cada valor está à esquerda, no pivô ou à direita. Portanto, a soma à direita é o total menos a soma à esquerda menos nums[i]. Para [3, 1, 5, 2, 2], o total é 13. No índice 0, a soma à esquerda é 0 e a soma à direita é 13 - 0 - 3 = 10. No índice 1, ela é 3 contra 9. No índice 2, é 4 contra 13 - 4 - 5 = 4, então você retorna 2.

A ordem dentro do loop importa. Compare primeiro e, em seguida, adicione nums[i] à soma à esquerda, para que ela nunca inclua o valor do índice que você está testando. Retornar na primeira correspondência fornece o pivô mais à esquerda.

Você lê o array duas vezes, uma vez para obter o total e outra para percorrê-lo, então o tempo é O(n). Apenas dois números são armazenados, então o espaço extra é O(1).

Algoritmo

Some todos os valores em total.
Defina left como 0.
Para cada índice i, se left for igual a total - left - nums[i], retorne i.
Caso contrário, adicione nums[i] a left e continue.
Se o loop terminar, retorne -1.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, value in enumerate(nums):
        # Everything that is not on the left and not nums[i] is on the right.
        if left == total - left - value:
            return i
        left += value
    return -1

Armadilhas e casos extremos

A maioria das respostas erradas coloca o próprio valor do pivô em um dos lados ou pula um índice de borda.

Adicionar nums[i] à soma da esquerda antes da comparação. O lado esquerdo então inclui o valor do pivô, e [3, 1, 5, 2, 2] deixa de encontrar o índice 2.
Calcular o lado direito como total - left. Isso conta nums[i] no lado direito; subtraia-o também.
Pular o índice 0 ou o último índice. Ambos podem ser o pivô, porque a soma de um lado vazio é 0. [1, -1, 1] retorna 0 e [4, -4, 9] retorna 2.
Retornar a última correspondência em vez da primeira. Em [0, 0, 0], todos os índices se equilibram, e a resposta é 0.
Usar dois ponteiros que se movem para dentro a partir das duas extremidades e aumentar o lado menor. Isso só funciona quando todos os valores são não negativos; aqui, os valores chegam a -1000, então um lado pode diminuir enquanto cresce.
Esquecer que os arrays em Lua e R começam em 1. Retorne i-1 para que a resposta seja um índice baseado em 0.

Perguntas frequentes4

Qual é a complexidade de tempo de Find Pivot Index?

A solução usando o total e a soma acumulada leva O(n) tempo: uma passagem para somar o array e outra para percorrê-lo. Ela usa O(1) de espaço extra. Recalcular os dois lados em cada índice leva O(n²) tempo.

Por que a soma à direita é igual ao total menos a soma à esquerda menos nums[i]?

Todo valor do array está exatamente em um de três lugares: à esquerda de i, em i ou à direita de i. As somas desses valores totalizam o total, então a soma à direita é o total menos as outras duas partes. Isso permite verificar um índice sem nunca somar o lado direito.

É possível resolver Find Pivot Index com dois ponteiros?

Não de forma confiável. Uma varredura com dois ponteiros que sempre aumenta o lado menor pressupõe que adicionar um valor torna um lado maior, o que deixa de funcionar assim que os valores podem ser negativos: um lado pode diminuir enquanto você o aumenta, então a varredura pode mover um ponteiro para além do pivô real. O método da soma acumulada não faz suposições sobre os sinais e verifica todos os índices.

Qual é o índice pivô de um array com um elemento?

É 0. Ambos os lados do único elemento estão vazios, e a soma de um lado vazio é 0, então os dois lados são iguais. A solução com soma acumulada retorna 0 na primeira comparação: o lado esquerdo é 0, e o total menos 0 menos o valor também é 0.

Python

def pivotIndex(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [3, 1, 5, 2, 2]

Esperado

Find Pivot Index

Função

Restrições

Exemplos

Dicas

Solução

Some os dois lados em cada índice

Soma prefixada

Soma total e soma acumulada à esquerda

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos