Running Sum of an Array

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

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

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

При переносе одного общего значения слева направо алгоритм работает за время O(n) , выполняя одно сложение для каждого элемента, и требует O(1) дополнительной памяти, не считая ответа. Повторное вычисление каждого префикса с самого начала требует n(n+1)/2 сложений, то есть 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].

+13 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

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

Это правильно, но здесь повторяются одни и те же действия. Подсчёт для индекса 4 начинается заново с nums[0], хотя подсчёт для индекса 3, 9, уже содержит сумму первых четырёх чисел. Для индекса i требуется i+1 сложений, поэтому для всего массива требуется 1 + 2 + ... + n = n(n+1)/2. При n = 5000 это около 1.25 × 10^7 сложений, хотя достаточно 5000.

Помимо массива ответов, который ты в любом случае возвращаешь, алгоритм хранит только сумму и два индекса, поэтому дополнительная память составляет O(1).

Алгоритм

Создай массив ответов длины 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] значение total последовательно равно 3, 4, 8, 9, 14, и эти пять значений и будут ответом. Каждый элемент читается один раз, и для него выполняется одно сложение, поэтому время работы составляет O(n). Помимо массива ответа, используется только переменная total, поэтому дополнительная память составляет O(1).

Здесь сумма не может превысить 5000 × 10^4 = 5 × 10^7, что помещается в 32-битное целое число. При больших входных данных префиксные суммы часто приводят к переполнению, поэтому 64-битное значение для суммы — безопасный вариант по умолчанию.

Алгоритм

Создай массив ответа длины 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] = result[i-1] + nums[i] без обработки i = 0. Индекс -1 выходит за границы массива в большинстве языков, а в Python это последний элемент, поэтому версия на месте, начинающаяся с 0, прибавляет последнее число к первому.
Остановка внутреннего цикла первого подхода при условии j < i. В результате пропускается nums[i], поэтому в каждом ответе не хватает одного числа.
Наращивание результата копированием. В R выражение result <- c(result, total) копирует весь вектор на каждом шаге, из-за чего быстрый подход снова становится квадратичным. Сначала выделите память под массив полной длины.
Забытый *returnSize = numsSize в C. Без него вызывающая сторона не знает, сколько сумм считывать.

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

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

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

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

При переносе одного общего значения слева направо алгоритм работает за время O(n), выполняя одно сложение для каждого элемента, и требует O(1) дополнительной памяти, не считая ответа. Повторное вычисление каждого префикса с самого начала требует n(n+1)/2 сложений, то есть 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).

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

[3, 4, 8, 9, 14]