Premium

Префиксные суммы

Сумма подмассива, равная k

Посчитать количество непрерывных подмассивов с суммой k

Средний

Постановка задачи

Описание (LeetCode)

Дан массив целых чисел nums и целое число k. Нужно вернуть количество непустых непрерывных подмассивов, сумма которых равна k.

Подмассив - это непрерывная часть исходного массива.

Пример 1:

nums = [1, 1, 1], k = 2

Результат:

2

Пояснение:

Есть два подходящих подмассива: [1, 1] на индексах 0..1 и [1, 1] на индексах 1..2.

Пример 2:

nums = [1, 2, 3], k = 3

Результат:

2

Пояснение:

Подходящие подмассивы: [1, 2] и [3].

Ограничения:

  • 1 <= nums.length <= 2 * 10⁴
  • -1000 <= nums[i] <= 1000
  • -10⁷ <= k <= 10⁷

Решение

Для решения этой задачи первая идея, которая приходит на ум - это перебор подмассивов. Можно выбрать левую границу, правую границу и посчитать сумму между ними. Но так мы быстро приходим к сложности O(n²), а если еще пересчитывать сумму каждый раз с нуля, то и к O(n³).

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

Идея решения:

Обозначим prefixSum как сумму элементов от начала массива до текущего индекса. Пусть мы сейчас на позиции r, и хотим понять, сколько подмассивов с правой границей в r имеют сумму k.

Перейдите на Premium, чтобы продолжить

Разблокируйте доступ к этой статье и всем остальным материалам с NowInterview Premium

Перейти на Premium