Find Pivot Index
Дан массив целых чисел nums. Индексом опоры называется индекс, для которого сумма значений слева от него равна сумме значений справа от него. Значение в самом индексе опоры не относится ни к одной из сторон, а сумма значений на стороне, где их нет, равна 0.
Верните самый левый индекс опоры или -1, если такого индекса нет.
Функция
- numsinteger-array
- массив целых чисел для балансировки
- Возвращаетinteger
- индекс самого левого опорного элемента или -1, если такого нет
Ограничения
1 ≤ nums.length ≤ 104-1000 ≤ nums[i] ≤ 1000
Примеры
- Ввод
- nums = [3, 1, 5, 2, 2]
- Вывод
- 2
- Пояснение
- В индексе 2 левая сторона равна 3 + 1 = 4, а правая сторона равна 2 + 2 = 4. Индексы 0 и 1 не уравновешены (слева 0 против 10, слева 3 против 9), поэтому 2 — самый левый опорный индекс.
- Ввод
- nums = [1, 2, 3]
- Вывод
- -1
- Пояснение
- Три кандидата дают 0 против 5, 1 против 3 и 3 против 0. Ни один индекс не уравновешивает значения, поэтому ответ —
-1.
- Ввод
- nums = [4, -4, 9]
- Вывод
- 2
- Пояснение
- При индексе 2 левая сторона равна 4 + (-4) = 0, а правая сторона пуста, поэтому её сумма также равна 0. Последний индекс может быть опорным.
+17 скрытых тестов при отправке
Дополнительный вопрос
Можешь найти самый левый опорный элемент, прочитав каждое значение только один раз, не вычисляя предварительно общую сумму? Сколько это требует памяти?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Для проверки одного индекса нужны две суммы: значения перед ним и значения после него. Повторное сложение этих значений для каждого индекса почти полностью дублирует работу. Как связаны две суммы для индекса
iс суммами для индексаi+1?При переходе на один шаг вправо к левой сумме добавляется
nums[i]. А когда известна сумма всего массива, правую сумму можно получить из левой: это общая сумма минус левая сумма минусnums[i].Сначала сложи все элементы массива. Затем пройди по нему слева направо, накапливая сумму слева. На каждом индексе сравни сумму слева с общей суммой минус сумма слева минус текущее значение; при первом совпадении верни индекс, и только после сравнения добавь текущее значение к сумме слева. Если цикл завершится, верни -1.
Решение
Проверка одного индекса требует двух сумм, но их пересчёт для каждого индекса увеличивает объём работы пропорционально квадрату длины. Решение — прекратить пересчёт: левая сумма на каждом шаге увеличивается на одно значение, а правая равна остатку от общей суммы. Один проход для вычисления общей суммы и второй проход с накапливаемой левой суммой позволяют найти самый левый опорный индекс, используя два числа в памяти.
Сложите обе стороны в каждом индексе
Верно, но не успевает на самых больших тестах
Идея
Следуй определению. Для каждого индекса i сложи значения перед ним, сложи значения после него и сравни суммы. Первый индекс, на котором суммы совпадают, и есть ответ, потому что индексы проверяются слева направо.
Крайние случаи обрабатываются сами собой. При индексе 0 левый цикл выполняется ноль раз, поэтому левая сумма равна 0; при последнем индексе правый цикл выполняется ноль раз. Поэтому [4, -4, 9] возвращает 2.
Проблема — в затратах. Для каждого индекса суммируются остальные n-1 значений, поэтому общий объём работы составляет примерно n² сложений. Для 10 000 значений это почти 100 миллионов сложений, и большинство из них повторно вычисляют суммы, которые уже были вычислены на шаг раньше.
Алгоритм
- Переберите все индексы
numsс помощью циклаi. - Сложите значения от
nums[0]доnums[i-1], чтобы получить левую сумму. - Сложите значения от
nums[i+1]до последнего значения, чтобы получить правую сумму. - Если суммы равны, верните
i. - Если подходящего индекса нет, верните -1.
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Массив префиксных сумм
Идея
Метод грубой силы снова и снова суммирует последовательности элементов массива. Массив префиксных сумм выполняет эту работу один раз. Пусть prefix[k] — сумма первых k значений, где prefix[0] = 0. Для [3, 1, 5, 2, 2] это [0, 3, 4, 9, 11, 13].
Теперь сумму любой последовательности можно получить как разность двух значений. Слева от индекса i находятся первые i значений, поэтому это prefix[i]. Справа находятся все значения после nums[i], то есть prefix[n] - prefix[i+1]. Для индекса 2 слева получаем 4, а справа — 13 - 9 = 4, значит, это точка опоры.
Построение массива требует одного прохода, а каждая проверка выполняется за постоянное время, поэтому весь поиск занимает O(n). Цена за это — n+1 дополнительных чисел в памяти.
Алгоритм
- Создайте
prefixдлиныn+1сprefix[0] = 0. - Заполните его:
prefix[k+1] = prefix[k] + nums[k]. - Для каждого индекса
iсчитайте левую сумму какprefix[i], а правую сумму какprefix[n] - prefix[i+1]. - Верните первый
i, для которого они равны, или -1 после цикла.
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Общая сумма и накапливаемая сумма слева
Идея
Посмотри, какие элементы префиксного массива читает предыдущий подход. При индексе i ему нужны prefix[i], prefix[i+1] и prefix[n]. Последний — это общая сумма, которая никогда не меняется, а две другие — текущая сумма, которая получилась бы, если пройти по массиву один раз. Поэтому вместо всего массива можно хранить общую сумму и одну текущую сумму слева.
Каждое значение находится слева, на месте опорного элемента или справа. Поэтому сумма справа равна общей сумме минус сумма слева минус nums[i]. Для [3, 1, 5, 2, 2] общая сумма равна 13. При индексе 0 сумма слева равна 0, а сумма справа равна 13 - 0 - 3 = 10. При индексе 1 это 3 против 9. При индексе 2 это 4 против 13 - 4 - 5 = 4, поэтому нужно вернуть 2.
Порядок действий в цикле важен. Сначала сравни суммы, а затем прибавь nums[i] к сумме слева, чтобы сумма слева никогда не включала значение по проверяемому индексу. Возврат при первом совпадении даёт самый левый опорный элемент.
Массив читается дважды: один раз для вычисления общей суммы и один раз для сканирования, поэтому время работы — O(n). Хранятся всего два числа, поэтому дополнительная память — O(1).
Алгоритм
- Сложи все значения и запиши результат в
total. - Присвой
leftзначение 0. - Для каждого индекса
i, еслиleftравноtotal - left - nums[i], верниi. - В противном случае добавь
nums[i]кleftи продолжай. - Если цикл завершится, верни -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
Ловушки и крайние случаи
В большинстве неправильных ответов собственное значение опорного элемента оказывается с одной из сторон либо пропускается крайний индекс.
- Добавление
nums[i]к левой сумме до сравнения. Тогда левая сторона включает значение опорного элемента, и[3, 1, 5, 2, 2]больше не находит индекс 2. - Вычисление правой стороны как
total - left. Такnums[i]учитывается справа; вычтите его и там. - Пропуск индекса 0 или последнего индекса. Любой из них может быть опорным, поскольку сумма пустой стороны равна 0. Для
[1, -1, 1]возвращается 0, а для[4, -4, 9]— 2. - Возврат последнего совпадения вместо первого. В
[0, 0, 0]баланс соблюдается для каждого индекса, и ответ — 0. - Использование двух указателей, которые движутся навстречу друг другу с обоих концов и увеличивают меньшую сторону. Это работает, только если все значения неотрицательны; здесь значения опускаются до -1000, поэтому сумма стороны может уменьшаться по мере её роста.
- Забывая, что индексация массивов в Lua и R начинается с 1. Возвращайте
i-1, чтобы получить индекс с отсчётом от 0.
Частые вопросы4
Какова временная сложность Find Pivot Index?
Решение с общей суммой и накопительной суммой работает за время O(n): один проход для суммирования массива и один проход для его просмотра. Оно использует O(1) дополнительной памяти. Повторное вычисление обеих частей на каждом индексе вместо этого занимает время O(n²).
Почему правая сумма равна общему значению минус левая сумма минус nums[i]?
Каждое значение массива находится ровно в одном из трёх мест: слева от i, на позиции i или справа от i. Их суммы в итоге дают общую сумму, поэтому сумма справа равна общей сумме за вычетом двух других частей. Это позволяет проверить индекс, ни разу не складывая значения справа.
Можно ли решить задачу «Найти индекс опорного элемента» с помощью двух указателей?
Ненадёжно. Сканирование двумя указателями, при котором всегда расширяется меньшая сторона, предполагает, что добавление значения делает сторону больше. Это предположение перестаёт работать, как только значения могут быть отрицательными: сторона может уменьшиться при расширении, поэтому сканирование может передвинуть указатель за настоящую точку поворота. Метод текущей суммы не делает предположений о знаках и проверяет каждый индекс.
Каков индекс опорного элемента массива, содержащего один элемент?
Это 0. Обе стороны единственного элемента пусты, а сумма пустой стороны равна 0, поэтому обе стороны равны. Решение с накопительной суммой возвращает 0 при первом сравнении: слева 0, а общая сумма минус 0 и минус значение тоже равна 0.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def pivotIndex(nums):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
nums = [3, 1, 5, 2, 2]
Ожидается
2