Различные подходы к решению Leetcode 724 в JavaScript
Есть бесчисленное множество способов подойти к этой проблеме и оптимизировать решение. В этой статье мы рассмотрим одну из этих стратегий для решения этой проблемы. Давайте сначала посмотрим на постановку задачи.
Постановка проблемы:
Учитывая массив целых чисел
nums
, вычислите основной индекс этого массива. Возвращает самый левый опорный индекс. Если такого индекса не существует, вернуть-1
.
Сводной индекс:
- Сводной индекс — это индекс, в котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго. > справа от указателя.
- Если индекс находится на левом краю массива, то левая сумма равна
0
, потому что слева нет элементов. Это также относится к правому краю массива.
Подход 1: сумма префиксов
Итак, идея состоит в том, чтобы вычесть известную левую сумму и текущий элемент из общей суммы входного массива. Перебирая входной массив и сравнивая левую сумму и правую сумму по каждому индексу, мы можем эффективно определить опорный индекс.
- Сначала мы вычисляем сумму всех элементов в данном массиве. Это делается путем перебора массива и добавления каждого элемента в переменную
totalSum
. - Затем мы инициализируем переменную
leftSum
для отслеживания суммы элементов слева от текущего индекса. - Далее мы перебираем массив с помощью цикла. Для каждого элемента с индексом
i
мы вычисляемrightSum
как разницу между totalSum, leftSum и текущим элементом nums[i]. .rightSum
представляет собой сумму элементов справа от текущего индекса. - Теперь сравним
leftSum
иrightSum
. Если они равны, значит, мы нашли опорный индекс, поэтому возвращаем текущий индексi
. - Если сводной индекс не найден, мы обновляем
leftSum
, добавляя к нему текущий элементnums[i]
, и переходим к следующей итерации. - Если после цикла не найден сводной индекс, мы возвращаем -1, чтобы указать, что в массиве нет сводного индекса.
// ES6 Arrow Function const pivotIndex = nums => { let totalSum = 0; for(let i of nums) totalSum += i; let leftSum = 0; for(let i = 0; i < nums.length; i++) { const rightSum = totalSum - leftSum - nums[i]; if(leftSum === rightSum) return i; leftSum += nums[i]; } return -1; }
Временная сложность: O(N)
У нас есть два цикла, оба используются для итерации входного массива размера N. Следовательно, временная сложность является линейной.
Космическая сложность: O(1)
Поскольку пространство не принадлежит размеру входного массива, оно является константой.
Я надеюсь, что эта статья предоставила вам ценную информацию и помогла вам лучше понять эту проблему. Удачного кодирования!
Проблема - Литкод 724