Подсчёт подмассивов с заданной суммой
Объединяйте префиксные суммы с хеш-таблицей
«Подсчёт подмассивов с заданной суммой» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Более сложный вопрос
А теперь усложним задачу: посчитайте, сколько подмассивов дают в сумме целевое значение k. Проверять каждую пару медленно, но префиксные суммы вместе с хеш-таблицей решают эту задачу. 🎯
Переформулируйте задачу через префиксные суммы
Сумма подмассива равна prefix[r + 1] минус prefix[l]. Поэтому сумма k означает, что два значения префиксных сумм отличаются ровно на k.
Главная перестановка
Если текущая префиксная сумма равна P, Вам нужна более ранняя префиксная сумма, равная P минус k. Вся идея заключается в этой перестановке.
need = current_prefix - kСчитайте, а не ищите
Вместо того чтобы каждый раз просматривать предыдущие элементы, запоминайте, сколько раз встречалось каждое значение префиксной суммы. Накопительный подсчёт даёт ответ за O(1).
Используйте таблицу частот
Словарь сопоставляет каждому значению префиксной суммы количество его появлений. Эта таблица превращает поиск в мгновенный подсчёт.
from collections import defaultdict
seen = defaultdict(int)Добавьте пустой префикс
До начала цикла запишите, что префиксная сумма 0 встретилась один раз. Эта начальная запись позволяет учитывать подмассивы, начинающиеся с индекса 0.
seen[0] = 1Цикл за один проход
Для каждого элемента обновите текущую префиксную сумму, добавьте количество нужного значения, а затем сохраните текущую префиксную сумму. Один проход делает всё.
total += x
count += seen[total - k]
seen[total] += 1Почему порядок важен
Сначала нужно добавить значение к ответу, а уже потом сохранить текущую префиксную сумму. Иначе появится диапазон нулевой длины и подсчёт будет неверным.
Преимущество по скорости
Для каждого элемента выполняется константное количество действий, поэтому весь подсчёт занимает O(n). На больших входных данных это быстрее полного перебора за O(n в квадрате).
Отрицательные числа тоже подходят
В отличие от скользящих окон, этот метод без проблем работает с отрицательными числами, потому что разности префиксных сумм остаются корректными при любых знаках.
Классический пример применения
Этот приём решает знаменитую задачу о подмассиве с суммой k и множество замаскированных вариантов на проверяющих системах соревнований.
Быстрая проверка
Текущая префиксная сумма равна P, а целевое значение — k.
Итоги
Теперь Вы умеете считать подмассивы с заданной суммой за O(n), используя префиксные суммы и таблицу частот. Сначала добавьте префиксную сумму 0, затем считайте и только после этого сохраняйте текущую. ✅
Часто задаваемые вопросы
Урок «Подсчёт подмассивов с заданной суммой» бесплатный?
Да — полный текст урока «Подсчёт подмассивов с заданной суммой» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Подсчёт подмассивов с заданной суммой»?
Объединяйте префиксные суммы с хеш-таблицей Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Подсчёт подмассивов с заданной суммой»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Построение массива префиксных сумм
- Сумма любого диапазона вычитанием
- Подсчёт подмассивов с заданной суммой
- Массивы разностей для обновлений диапазонов