Где применяется
1. Задача
Дан список чисел. Сколько в нём отрезков из чисел подряд, сумма которых ровно k? В прошлом уроке префиксные суммы давали сумму любого отрезка одним вычитанием. Теперь из этого получится способ считать отрезки. Это первая задача, где нужно узнать «сколько отрезков обладают этим свойством», а не одну сумму. Медленный способ перебирает каждое начало и каждый конец, это O(n2). Способ через префиксные суммы считает все отрезки за один проход. Он работает даже с отрицательными числами, на которых скользящее окно незаметно ломается.
2. Простыми словами
Возьми тестовый список [3, 4, 7, 2] и k = 7. Запиши накопленную сумму после каждого числа: 3, 7, 14, 16. До первого числа сумма равна 0. Нужны все отрезки из чисел подряд, которые в сумме дают 7.
Пересчитывать ничего не нужно. После каждого числа смотришь, встречалась ли раньше сумма «текущая сумма минус 7». После 2-го числа сумма 7, ищешь 0: это сумма до первого числа, она была. Значит, 3 и 4 вместе дают 7. После 3-го числа сумма 14, ищешь 7: она была после 2-го числа. Значит, число 7 само по себе даёт 7. После 4-го числа сумма 16, ищешь 9: такой суммы не было.
Поэтому ты ведёшь учёт: какие суммы уже встречались и сколько раз. Ответ, здесь это 2, набирается за один проход.
3. Идея
Иди по списку и веди накопленную сумму. После каждого числа она равна префиксной сумме этой позиции. Сумма любого отрезка равна разности двух префиксных сумм: сумма в его конце минус сумма прямо перед его началом. Значит, отрезок даёт в сумме k ровно тогда, когда какая-то прежняя префиксная сумма равна текущей сумме минус k. Отсюда число подходящих отрезков, которые заканчиваются на текущей позиции: это сколько раз раньше встречалась префиксная сумма sum - k.
Чтобы отвечать сразу, храни карту: значение префиксной суммы → сколько раз оно встречалось. На каждом элементе прибавь его к sum, посмотри, сколько раз встречалось sum - k, и прибавь это к счётчику. Потом запиши текущий sum в карту. Начни карту с {0: 1}. До первого элемента сумма равна 0 (пустое начало списка). Благодаря этой записи отрезок, который начинается с самого начала списка, тоже будет посчитан.
Проследим на [1, 2, 3] при k = 3. Начало: seen = {0: 1}, sum = 0, count = 0.
- Элемент 1:
sum = 1. Ищем1 - 3 = -2: не встречалось, +0. Записываем:seen = {0:1, 1:1}. - Элемент 2:
sum = 3. Ищем3 - 3 = 0: встречалось 1 раз, +1,countстал 1. Записываем3:1. - Элемент 3:
sum = 6. Ищем6 - 3 = 3: встречалось 1 раз, +1,countстал 2. Записываем6:1.
Ответ 2: отрезки [1, 2] и [3].
4. Во что это обходится
Время O(n): один проход, и каждый поиск и каждая запись в карту стоят в среднем O(1). Память O(n) на карту в худшем случае, когда все префиксные суммы разные. Это выигрыш по сравнению с двойным циклом за O(n2): немного памяти в обмен на целый множитель n по времени. Скользящему окну из прошлых уроков нужны неотрицательные числа. Этому способу они не нужны: отрицательные числа и нули обрабатываются без дополнительного кода. Он сравнивает префиксные суммы и не расширяет и не сужает окно.
6. Где это встречается
Подсчёт периодов, за которые баланс в реестре операций не изменился (сумма изменений равна нулю). Отрезки сигнала, сумма которых равна цели. Подмассивы с заданным XOR (тот же приём, только XOR вместо суммы). Сколько раз метрика возвращалась к прежнему уровню. Идея «префиксная сумма плюс карта» работает не только для сумм. Если свойство диапазона равно разности двух накопленных значений, такие диапазоны можно посчитать или найти за один проход. Для этого достаточно помнить накопленные значения, которые уже встречались. Так решается целый ряд задач вида «посчитай подмассивы, где...».
На LeetCode
Задачи, где нужно посчитать подмассивы с суммой ровно k или кратной k, даже когда есть отрицательные числа. Держи бегущую сумму и Map с тем, сколько раз встречалась каждая такая сумма.
Это задача урока, и seen так же начинается с {0: 1}.
Тот же подсчёт по нулям и единицам, только вместо k здесь goal.
Храни бегущие суммы по остатку от деления на k, а отрицательный остаток исправляй, прибавляя k.
Считай 0 как минус 1 и храни первый индекс каждой бегущей суммы, ведь самый длинный отрезок с суммой 0 лежит между двумя равными.
Твоя задача (Tier 1)
Напиши функцию subarraySumCount(nums, k).
Посчитай, сколько отрезков из чисел подряд дают в сумме k. Веди накопленную сумму и карту, где записано, сколько раз встречалась каждая накопленная сумма.
- Вход:
nums, список чисел (могут быть отрицательными), иk, целевая сумма. Пример:[1, 1, 1],2. - Возвращает: сколько отрезков из чисел подряд дают в сумме
k.
Шаги:
- Заведи карту
seenи положи в неё{0: 1}: до начала списка накопленная сумма равна0, и это один случай. Задайsum = 0иcount = 0. - Иди по списку. Прибавляй каждое число к
sum. - Найди
sum - kвseenи прибавь записанное там число кcount. Так ты считаешь отрезки, которые заканчиваются здесь и дают в суммеk. - Прибавь 1 к записи для
sumвseen. Поиск из шага 3 делай до этого шага. В конце верниcount.
Готово, когда проходят все тесты:
[1, 1, 1],2->2[1, 2, 3],3->2[3, 4, 7, 2],7->2[1, -1, 0],0->3(отрицательные)[0, 0, 0],0->6(много пересекающихся отрезков)[1],0->0(ни один отрезок не подходит)[],0->0(пустой список)
Практика
Count subarrays summing to k (prefix sums + a hash map of counts)
subarraySumCount(nums, k) -> number of contiguous subarrays whose sum is exactly k
export function subarraySumCount(nums, k) {
// Your code here. The task is described in the box above the editor.
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.
Лестница подсказок
Застрял? Открывай по одной, но сначала попробуй сам.