Range Sum Query - Immutable

Лёгкая№303сумма подмассива

Нужно написать класс: он один раз получает массив чисел и потом отвечает на много запросов — сумма чисел с индекса left по индекс right включительно. Массив не меняется. Наш пример: [4, -2, 3, 5, -1, 2] и три запроса — sumRange(2, 4) = 7, sumRange(0, 3) = 10 и sumRange(1, 1) = -2.

303 Range Sum Query - ImmutableРазбор · 1×

Пример: [4, -2, 3, 5, -1, 2], затем sumRange(2, 4), sumRange(0, 3), sumRange(1, 1). Под числами — префиксные суммы: prefix[j] стоит перед nums[j] и хранит сумму всего, что левее.

numsprefix4-235-12
ещё не заполненоготовая префиксная сумматекущееprefix[left], вычитаемотрезок запроса

Создаём NumArray([4, -2, 3, 5, -1, 2]): init выполняется один раз

01/20
сначала · назад · пуск · шаг
Скорость
1class NumArray:
2 function init(nums):
3 prefix = array of len(nums) + 1 zeros
4 for i from 0 to len(nums) - 1:
5 prefix[i + 1] = prefix[i] + nums[i]
6 function sumRange(left, right):
7 return prefix[right + 1] - prefix[left]
состояние
prefix
–
i
–
left
–
right
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. prefix[j] — сумма первых j чисел. Числа с left по right — это первые right + 1 чисел без первых left, поэтому их сумма равна prefix[right + 1] − prefix[left].
  2. Лишняя ячейка prefix[0] = 0 — сумма пустого начала: запрос с индекса 0 вычитает её, и особый случай не нужен.
  3. Массив не меняется, поэтому таблица, построенная один раз, верна для всех запросов, а каждый запрос — два обращения, какой бы длинный ни был отрезок.

Сложность

init: время O(n) и память O(n) на n + 1 сумму. Каждый sumRange: время O(1), два обращения и вычитание.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.