Índice do ponto de equilíbrio
A missão
Problema
Dada uma lista de números inteiros, que podem ser negativos, encontre uma posição em que os valores estritamente à sua esquerda somam o mesmo total que os valores estritamente à sua direita. Um lado vazio conta como zero. Retorne o índice mais à esquerda com essa propriedade, ou -1 se não houver nenhum.
Exemplos
Input: values = [2, 7, 1, 5, 4]
Output: 2
Por quê: 2 + 7 = 9 à esquerda do índice 2, e 5 + 4 = 9 à direita
Input: values = [1, 2, 3]
Output: -1
Por quê: nenhum índice divide a lista em lados iguais
Input: values = [5]
Output: 0
Por quê: edge case: os dois lados do único valor estão vazios e somam 0
Dicas
0 / 3
Recalcular a soma dos dois lados desde o início em cada índice repete as mesmas adições várias vezes, o que torna a verificação inteira quadrática.
Depois que você sabe o total da lista inteira, o lado direito em qualquer índice pode ser deduzido do lado esquerdo e do valor nesse índice.
Some a lista uma vez. Depois, percorra-a com um total acumulado da esquerda: o total da direita é o total geral menos o total da esquerda menos o valor atual. Retorne o primeiro índice em que eles coincidem e some o valor atual ao total da esquerda antes de seguir.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- values may be negative
Solução
Uma passada calcula o total geral, e uma segunda passada mantém uma soma acumulada de tudo o que já ficou para trás. Em cada índice, o lado direito é o que sobra do total depois de tirar o lado esquerdo e o valor atual, então cada verificação é O(1) em vez de O(n). O primeiro índice que bate é retornado, e por isso ele é o mais à esquerda. O tempo é O(n), e o espaço extra é O(1).
def balance_point(values):
total = sum(values)
left = 0
for i, v in enumerate(values):
right = total - left - v # everything after index i
if left == right:
return i
left += v
return -1
print(balance_point([2, 7, 1, 5, 4])) # -> 2
print(balance_point([1, 2, 3])) # -> -1
print(balance_point([5])) # -> 0Travou na ideia, e não no código? O(1) e O(n) explica isso.