Find Pivot Index

Лёгкая№724сумма подмассива

Дан массив чисел. Нужно найти опорный индекс: сумма чисел строго левее него равна сумме чисел строго правее, а у пустой стороны сумма 0. Если таких индексов несколько — вернуть самый левый, если нет ни одного — вернуть -1. Наш пример: [3, -1, 4, 9, 2, 5, -1] — ответ 3: левее девятки 3 - 1 + 4 = 6, правее неё 2 + 5 - 1 = 6.

724 Find Pivot IndexРазбор · 1×

Пример: [3, -1, 4, 9, 2, 5, -1]. Под числами — left в каждом промежутке, до которого он дошёл; ниже — суммы двух сторон от i.

numsleft3-14925-1
ещё не дошлилевее i, в leftтекущееправее i, в rightопорный индекс

Один раз складываем все числа: total = 21

01/18
сначала · назад · пуск · шаг
Скорость
1function pivotIndex(nums):
2 total = sum(nums)
3 left = 0
4 for i from 0 to len(nums) - 1:
5 right = total - left - nums[i]
6 if left == right:
7 return i
8 left = left + nums[i]
9 return -1
состояние
total
21
left
–
i
–
right
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Для любого i: left + nums[i] + right = total. Значит, right = total − left − nums[i]: одна сумма в начале даёт правую сторону у каждого индекса, складывать её заново не нужно.
  2. left растёт на одно число за шаг — это и есть накопленная префиксная сумма, ни один отрезок не складывается дважды.
  3. Проверка идёт до того, как nums[i] уходит в left, поэтому число на i не входит ни в одну сторону. Индексы проверяются слева направо, значит, первое совпадение — самый левый опорный индекс.

Сложность

Время O(n): один проход ради total и один в поисках индекса. Память O(1): только total и left, массив префиксных сумм не нужен.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.