Алгозадачи 2: указатели, окна и префиксы

Уровень medium пугает, пока не заметишь: за сотнями задач стоит короткий список паттернов. В этом уроке четыре главных: два указателя, скользящее окно, префиксные суммы и группировка по ключу. Каждый разбираем на канонической задаче, а в упражнениях тот же паттерн встретится в новой обёртке.

Как узнавать паттерн

Грубая карта соответствий, к которой мы будем возвращаться:

Слышишь в условии	Думаешь
отсортированный массив, пара или тройка с условием	два указателя
самая длинная или короткая непрерывная подстрока или подотрезок	скользящее окно
сколько подотрезков с заданной суммой или свойством	префиксные суммы плюс таблица
сгруппируй, посчитай уникальные, найди одинаковые	таблица с умным ключом

Это не заклинание, а первый ход в размышлении. Дальше, как обычно, инварианты и границы.

Два указателя: тройки с нулевой суммой

Найти все уникальные тройки, дающие в сумме ноль. Задача 3Sum, встречает соискателей на входе примерно везде.

Наивный перебор троек это O(n³). Ключевой ход: отсортировать. В отсортированном массиве пару с нужной суммой ищут два указателя за линию: сумма мала, двигаем левый, велика, правый.

Сортировка O(n log n), затем для каждого первого элемента линейный проход: итого O(n²), и лучше для этой задачи не бывает. Пропуски дублей выглядят вознёй, но именно они отличают принятое решение от отклонённого: без них результат содержит одинаковые тройки.

Тройки складываем кортежами. Дальше их можно класть в множество или сравнивать через =, потому что кортежи, как ты помнишь, равны по содержимому.

Скользящее окно: подстрока без повторов

Длина самой длинной подстроки без повторяющихся символов. Каноническая задача про скользящее окно.

Окно держит инвариант «внутри нет повторов». Правый край идёт по строке, таблица помнит последнюю позицию каждого байта. Встретили байт, который уже есть в окне, значит левый край перепрыгивает за его прошлую позицию:

Проверка (>= prev start) существенна: байт мог встречаться давно, левее окна, тогда он не мешает. Оба указателя двигаются только вперёд, значит время O(n), память O(1), таблица не может вырасти больше 256 ключей.

Сравни с лобовым O(n²), где каждая стартовая позиция проверяется заново. Окно выигрывает за счёт того, что не выбрасывает знание: всё, что мы узнали о повторах, переносится на следующий шаг.

Префиксные суммы: отрезки с суммой k

Сколько непрерывных подотрезков массива дают в сумме ровно k? Числа бывают отрицательными, значит окно не подойдёт: расширение окна не обязано увеличивать сумму, инвариант не удержать.

Работает другой паттерн. Префиксная сумма отрезка с j по i это префикс до i минус префикс до j. Хотим сумму k, значит ищем, сколько раз раньше встречался префикс «текущий минус k». Это снова задача про пару, и решает её снова таблица, как в Two Sum:

Стартовая запись @{0 1} говорит: пустой префикс с суммой ноль встречался один раз. Без неё потеряются отрезки, начинающиеся с нулевого индекса. Время O(n), и заметь родословную: это Two Sum, надетый на префиксы.

Группировка: анаграммы пачками

Сгруппировать слова так, чтобы анаграммы оказались вместе. Задача Group Anagrams, и в Janet она решается неприлично коротко.

Весь вопрос в ключе группы. Анаграммы становятся неразличимы, если отсортировать их байты:

string/bytes раскладывает строку в кортеж байтов, sorted сортирует, ; из урока про поток выполнения рассыпает массив в аргументы string/from-bytes. Дальше стандартная библиотека делает всё сама:

Императивная версия того же самого, если захочется увидеть механизм без магии:

Паттерн шире, чем одна задача: придумай ключ, при котором эквивалентные вещи совпадают, и таблица сгруппирует за тебя. Для точек это пара координат кортежем, для дат день без времени, для чисел остаток от деления.

Интервалы: слить пересекающиеся

Дан массив интервалов, слить пересекающиеся. Задача Merge Intervals, любимый вопрос про календари и брони.

После сортировки по началу вся задача сводится к одному проходу: очередной интервал либо пересекается с последним в ответе, либо открывает новый:

Интервалы в ответе лежат массивами, а не кортежами, ровно потому, что мы расширяем их на месте через put. Это осознанный выбор из урока про значения: изменяемость там, где она локальна и удобна.

Тот же алгоритм в функциональной записи это reduce, где аккумулятором служит массив результата. Попробуй переписать сам и реши, какая версия честнее говорит о происходящем.

Что запомнить

• Отсортированный массив плюс условие на пару или тройку: два указателя навстречу, каждый шаг исключает элемент.
• Непрерывный отрезок с инвариантом: скользящее окно, оба края двигаются только вперёд.
• Подотрезки с заданной суммой при отрицательных числах: префиксные суммы и таблица «префикс, сколько раз», это Two Sum на префиксах.
• Группировка это выбор ключа, при котором эквивалентное совпадает. Сортированные байты для анаграмм, кортеж для координат.
• Интервалы: сортировка по началу, затем один проход со слиянием.
• Гибридный стиль легален: reduce снаружи, локальная мутация внутри. Критерий один, читаемость.

Упражнения

Дальше

Остался последний уровень: задачи, где нужна структура посерьёзнее таблицы. Графы и обходы, куча из урока про структуры и динамическое программирование.