Код Senior Префиксные суммы обновлено
Число подмассивов с суммой k
Условие
Сколько непрерывных подмассивов имеют сумму ровно k (числа могут быть отрицательными).
Примеры
subarraySum([1, 1, 1], 2) // 2
subarraySum([1, 2, 3], 3) // 2
subarraySum([1, -1, 0], 0) // 3
Как подойти
Признак «сколько подмассивов с суммой X» + отрицательные числа → префиксные суммы в Map. Начальная запись {0:1} отвечает за подмассивы, начинающиеся с нуля. O(n).
Подсказки: 3
- Сумма отрезка = pre[right] - pre[left].
- Храни, сколько раз встречалась каждая префиксная сумма. Не забудь про ноль.
- Отрицательные числа убивают скользящее окно - поэтому именно префиксные суммы.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.