Различные подходы к решению Leetcode 724 в JavaScript

Есть бесчисленное множество способов подойти к этой проблеме и оптимизировать решение. В этой статье мы рассмотрим одну из этих стратегий для решения этой проблемы. Давайте сначала посмотрим на постановку задачи.

Постановка проблемы:

Учитывая массив целых чисел nums, вычислите основной индекс этого массива. Возвращает самый левый опорный индекс. Если такого индекса не существует, вернуть -1.

Сводной индекс:

  • Сводной индекс — это индекс, в котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго. > справа от указателя.
  • Если индекс находится на левом краю массива, то левая сумма равна 0, потому что слева нет элементов. Это также относится к правому краю массива.

Подход 1: сумма префиксов

Итак, идея состоит в том, чтобы вычесть известную левую сумму и текущий элемент из общей суммы входного массива. Перебирая входной массив и сравнивая левую сумму и правую сумму по каждому индексу, мы можем эффективно определить опорный индекс.

  1. Сначала мы вычисляем сумму всех элементов в данном массиве. Это делается путем перебора массива и добавления каждого элемента в переменную totalSum.
  2. Затем мы инициализируем переменную leftSum для отслеживания суммы элементов слева от текущего индекса.
  3. Далее мы перебираем массив с помощью цикла. Для каждого элемента с индексом i мы вычисляем rightSum как разницу между totalSum, leftSum и текущим элементом nums[i]. . rightSum представляет собой сумму элементов справа от текущего индекса.
  4. Теперь сравним leftSum и rightSum. Если они равны, значит, мы нашли опорный индекс, поэтому возвращаем текущий индекс i.
  5. Если сводной индекс не найден, мы обновляем leftSum, добавляя к нему текущий элемент nums[i], и переходим к следующей итерации.
  6. Если после цикла не найден сводной индекс, мы возвращаем -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