Выбор ответа Middle Префиксные суммы спрашивают часто обновлено
Количество подмассивов с суммой k
Вопрос
Массив содержит и отрицательные числа. Нужно посчитать подмассивы с суммой ровно k. Какой подход оптимален?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Префиксная сумма и Map «префикс → сколько раз встречался». Подмассив (i, j] имеет сумму k, если pre[j] - pre[i] = k, то есть pre[i] = pre[j] - k.
Варианты ответа
- Скользящее окно с суммой, сжимая слева при превышении k, O(n)
- Перебор всех подмассивов с префиксными суммами, O(n²)
- Префиксная сумма и Map «префикс → сколько раз встречался»правильный ответ
- Сортировка и два указателя навстречу, O(n log n)
Разбор
Подмассив (i, j] имеет сумму k, если pre[j] - pre[i] = k, то есть pre[i] = pre[j] - k. Идём слева направо, считаем, сколько раз раньше встречался префикс cur - k. Начальное значение map.set(0, 1). O(n) времени, O(n) памяти.
- Окно не работает с отрицательными числами: сумма немонотонна.
- Перебор верен, но O(n²).
- Сортировка ломает непрерывность.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.