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