Подсчёт окон, удовлетворяющих правилу
Приём: не более K минус не более K−1
«Подсчёт окон, удовлетворяющих правилу» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Подсчёт, а не измерение
Иногда требуется посчитать подмассивы, удовлетворяющие правилу, а не найти самый длинный. Небольшой приём превращает такую задачу в простой вариант работы со скользящим окном. 🔢
Задача с точным количеством K
Непосредственно считать подмассивы с ровно K вхождениями некоторого свойства неудобно. Граница постоянно меняется, поэтому построить одно аккуратное окно сложно.
Переход к «не более»
Подсчитывать подмассивы, содержащие не более K элементов нужного типа, с одним окном гораздо проще. При расширении вправо каждая допустимая левая граница задаёт один учитываемый подмассив.
Приём с вычитанием
Ровно K равно atMost(K) минус atMost(K - 1). Два простых подсчёта объединяются в нужный Вам сложный подсчёт.
answer = at_most(k) - at_most(k - 1)Создайте вспомогательную функцию
Напишите одну функцию, которая считает подмассивы, содержащие не более k элементов нужного типа. Она перемещает окно и уменьшает его, когда количество превышает k.
def at_most(k):
left = 0
total = 0Уменьшайте при нарушении
Расширяйте окно вправо и обновляйте его состояние. Пока оно содержит больше k элементов нужного типа, перемещайте левую границу вперёд, возвращая окно в допустимый диапазон.
while count > k:
# remove a[left]
left += 1Добавьте количество подмассивов окна
После исправления окна любой подмассив, заканчивающийся в правой границе и начинающийся от левой границы или правее, является допустимым. Добавьте правую границу минус левую плюс один.
total += right - left + 1Почему этот подсчёт работает
Для фиксированной правой границы допустимые начала — это левая граница, left+1 и так далее до right. В точности получается right - left + 1 подмассивов, каждый из которых удовлетворяет условию «не более k».
Объедините два вызова
Запустите вспомогательную функцию дважды и вычтите результаты. Каждый вызов выполняется за O(n), поэтому полный подсчёт подмассивов с ровно K элементами также имеет линейную сложность.
return at_most(k) - at_most(k - 1)Обработайте крайний случай
При k, равном нулю, atMost(k - 1) использовало бы отрицательное единицу. Обработайте этот случай, чтобы вспомогательная функция по-прежнему возвращала осмысленный нулевой результат.
Где это применяется
Идея at-most минус at-most подходит для подсчёта подмассивов с ровно K различными значениями, K нечётными элементами или любым другим монотонным свойством окна.
Быстрая проверка
Вы хотите посчитать подмассивы, содержащие ровно K различных элементов.
Итоги
Подсчёт подмассивов с ровно K элементами — это просто atMost(K) минус atMost(K - 1). Каждая вспомогательная функция перемещает окно за O(n), поэтому общая сложность остаётся линейной. ✅
Часто задаваемые вопросы
Урок «Подсчёт окон, удовлетворяющих правилу» бесплатный?
Да — полный текст урока «Подсчёт окон, удовлетворяющих правилу» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Подсчёт окон, удовлетворяющих правилу»?
Приём: не более K минус не более K−1 Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Подсчёт окон, удовлетворяющих правилу»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Суммы окон фиксированного размера
- Окно переменного размера с двумя указателями
- Самая длинная подстрока без повторов
- Подсчёт окон, удовлетворяющих правилу