Контест Middle Префиксные суммы спрашивают часто обновлено
Число подотрезков с суммой K
Условие
Дан массив целых чисел (есть и отрицательные) и число K. Посчитайте, сколько непустых подотрезков [l, r] имеют сумму ровно K.
Ввод: в первой строке n и K (1 ≤ n ≤ 2500, |K| ≤ 10¹⁴), во второй n чисел (|aᵢ| ≤ 10⁹).
Вывод: количество подотрезков.
Пример 1
Ввод:
5 3
1 2 1 -1 3
Вывод:
5
Пример 2
Ввод:
3 0
0 0 0
Вывод:
6
Как подойти
Подсказки: 2
- Сумма подотрезка = разность двух префиксных сумм.
- Окно не подойдёт: числа бывают отрицательными.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.