Running Sum of an Array

Q: Что такое накопительная сумма массива?

Это второй массив, в котором каждый элемент — сумма всех элементов до той же позиции включительно в первом массиве. Он также называется префиксной суммой или накопительной суммой. Накопительная сумма для [3, 1, 4, 1, 5] — это [3, 4, 8, 9, 14] .

Q: Какова временная сложность вычисления скользящей суммы?

Время O(n) при одном общем накопительном значении слева направо и дополнительная память O(1) , не считая ответа. Повторное вычисление каждого префикса с начала занимает O(n²) .

Q: Можешь вычислить накопительную сумму на месте?

Да. Пройдите от индекса 1 до конца и установите nums[i] += nums[i-1] . К этому моменту nums[i-1] уже содержит сумму всех элементов до него, поэтому каждый элемент в итоге станет своей префиксной суммой. Исходные значения будут потеряны.

Q: Как префиксные суммы помогают вычислять сумму на отрезке?

Сумма элементов среза nums[l..r] равна prefix[r] - prefix[l-1] или prefix[r] , если l = 0 . Для [3, 4, 8, 9, 14] сумма элементов с индексами от 2 до 4 равна 14 - 4 = 10 . После одного прохода за O(n) каждый запрос выполняется за O(1) .

НовичокПрефиксные суммы

+10

Тебе дан массив целых чисел nums. Верни новый массив той же длины, элемент с индексом i в котором равен nums[0] + nums[1] + ... + nums[i], то есть сумме первых i+1 чисел.

Функция

runningSum(nums: integer-array) → integer-array

numsinteger-array: числа, которые нужно сложить слева направо
Возвращаетinteger-array: текущие итоги — по одному для каждого элемента nums

Ограничения

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Каждая текущая сумма помещается в 32-битное целое число со знаком.

Примеры

Ввод: nums = [3, 1, 4, 1, 5]
Вывод: [3, 4, 8, 9, 14]
Пояснение: Продолжай складывать: 3, затем 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 и 9 + 5 = 14. Каждая сумма помещается в индекс числа, добавленного последним.

Ввод: nums = [-2, 5, -3]
Вывод: [-2, 3, 0]
Пояснение: Отрицательные числа уменьшают итоговое значение: -2, затем -2 + 5 = 3, затем 3 + (-3) = 0.

Ввод: nums = [7]
Вывод: [7]
Пояснение: У одного числа есть один текущий итог — оно само, поэтому ответ: [7].

Дополнительный вопрос

Можешь построить то же самое для сетки, где каждая ячейка содержит сумму значений прямоугольника от верхнего левого угла до этой ячейки?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждый ответ — это сумма префикса массива nums, а соседние префиксы отличаются одним элементом. Повторный расчёт каждого префикса с самого начала приводит к повторению почти всей работы. Вместо этого переноси вперёд одно общее значение — тогда для каждого ответа потребуется всего одно сложение.

Сложите каждый префикс с нуля

Идея

Следуй определению: для каждого индекса i начни с общей суммы 0, прибавь nums[0] до nums[i] включительно и сохрани результат. Это правильно, потому что каждый ответ вычисляется точно так, как определено.

Для индекса i требуется i+1 операций сложения, поэтому для массива потребуется n(n+1)/2: около 1.25 × 10^7 операций сложения при n = 5000, чего должно хватить.

Алгоритм

Создайте массив ответов длины n.
Для каждого индекса i задайте total = 0.
Прибавьте nums[j] к total для каждого j от 0 до i.
Сохраните total по индексу i в массиве ответов и верните массив ответов после последнего индекса.

def runningSum(nums):
    result = []
    for i in range(len(nums)):
        total = 0
        for j in range(i + 1):
            total += nums[j]
        result.append(total)
    return result

Ведите текущую сумму

Идея

Сумма первых i+1 чисел равна сумме первых i чисел плюс nums[i]: result[i] = result[i-1] + nums[i]. Поэтому тебе никогда не нужно заглядывать назад больше чем на один шаг, и достаточно одной переменной total. Для [3, 1, 4, 1, 5] получаются значения 3, 4, 8, 9, 14 — это и есть ответ.

Для каждого элемента требуется одно сложение: время O(n) и дополнительная память O(1), не считая ответа.

Алгоритм

Создай массив ответов длины n и задай total = 0.
Пройди по индексам слева направо и добавляй nums[i] к total.
Запиши total в индекс i массива ответов.
Верни массив ответов.

def runningSum(nums):
    result = []
    total = 0
    for num in nums:
        total += num
        result.append(total)
    return result

Ловушки и крайние случаи

Сброс total внутри цикла. Каждый ответ становится просто nums[i], а [3, 1, 4] возвращается без изменений.
Чтение result[i-1] при i = 0. В большинстве языков происходит выход за границы; Python читает последний элемент, поэтому версия с изменением исходного массива добавляет последнее число к первому.
Остановка внутреннего цикла грубой силы при j < i. При этом пропускается nums[i], поэтому в каждом ответе не хватает одного числа.
В R наращивание ответа с помощью result <- c(result, total) копирует вектор на каждом шаге и делает быстрый подход квадратичным. Сначала выделите память для массива полной длины.
В C забыть про *returnSize = numsSize. Тогда вызывающая сторона не будет знать, сколько итоговых значений нужно прочитать.

Частые вопросы4

Что такое накопительная сумма массива?

Это второй массив, в котором каждый элемент — сумма всех элементов до той же позиции включительно в первом массиве. Он также называется префиксной суммой или накопительной суммой. Накопительная сумма для [3, 1, 4, 1, 5] — это [3, 4, 8, 9, 14].

Какова временная сложность вычисления скользящей суммы?

Время O(n) при одном общем накопительном значении слева направо и дополнительная память O(1), не считая ответа. Повторное вычисление каждого префикса с начала занимает O(n²).

Можешь вычислить накопительную сумму на месте?

Да. Пройдите от индекса 1 до конца и установите nums[i] += nums[i-1]. К этому моменту nums[i-1] уже содержит сумму всех элементов до него, поэтому каждый элемент в итоге станет своей префиксной суммой. Исходные значения будут потеряны.

Как префиксные суммы помогают вычислять сумму на отрезке?

Сумма элементов среза nums[l..r] равна prefix[r] - prefix[l-1] или prefix[r], если l = 0. Для [3, 4, 8, 9, 14] сумма элементов с индексами от 2 до 4 равна 14 - 4 = 10. После одного прохода за O(n) каждый запрос выполняется за O(1).

def runningSum(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

nums = [3, 1, 4, 1, 5]

Ожидаемый вывод

[3, 4, 8, 9, 14]