Два указателя и скользящее окно: оптимизация перебора в массивах и строках

Метод двух указателей: классификация паттернов и переход от квадратичной сложности к линейной

Представьте массив из 100 000 записей о банковских транзакциях, отсортированных по времени. Система безопасности ищет две конкретные транзакции, сумма которых с точностью до копейки совпадает с подозрительным переводом в 1 000 000 рублей. Очевидное решение — взять первую транзакцию и сложить её по очереди со всеми остальными, затем взять вторую и повторить процесс. Для 100 000 элементов этот вложенный цикл совершит около 5 миллиардов проверок. На Python это займет несколько секунд. Если транзакций будет миллион — вычисления растянутся на часы. Алгоритм работает со сложностью $O(N^2)$, и для высоконагруженных систем это неприемлемо.

Проблема кроется не в языке программирования, а в избыточности самого перебора. Мы проверяем пары, которые заведомо не могут дать нужного результата. Чтобы избавиться от лишней работы и снизить сложность до $O(N)$, алгоритмика предлагает элегантный подход, не требующий сложных структур данных — метод двух указателей.

Анатомия указателя в Python

В языках вроде C или C++ указатель — это переменная, хранящая физический адрес в оперативной памяти. В контексте алгоритмических собеседований по Python термин «указатель» (pointer) используется в абстрактном смысле. Здесь указатель — это просто целочисленная переменная-индекс, которая указывает на текущую позицию в массиве или строке.

Обычно мы используем один неявный указатель, когда пишем цикл for i in range(len(arr)). Переменная i бежит по массиву слева направо. Метод двух указателей вводит вторую переменную-индекс — j, left, right, slow или fast. Управляя движением этих двух индексов по определенным правилам, мы можем анализировать пары элементов, подмассивы или сравнивать две разные последовательности за один проход.

Главная сила этого метода заключается в оптимизации вспомогательной памяти. Поскольку мы храним только два целых числа (индексы), пространственная сложность алгоритма остается $O(1)$, независимо от размера входных данных.

Как два указателя ломают квадратичную сложность

Чтобы понять механику перехода от $O(N^2)$ к $O(N)$, необходимо рассмотреть концепцию сокращения пространства поиска (search space pruning).

Вернемся к задаче поиска двух чисел с заданной суммой. Пусть дан отсортированный массив [2, 7, 11, 15] и целевая сумма 18. Пространство поиска — это все возможные пары индексов $(i, j)$. Их можно представить в виде двумерной матрицы, где строки — это левый элемент пары, а столбцы — правый. При квадратичном переборе мы добросовестно проверяем каждую ячейку этой матрицы.

Метод двух указателей использует свойства данных (в данном случае — отсортированность), чтобы отбрасывать целые строки и столбцы этой матрицы за одну операцию. Если сумма элементов на текущих указателях больше целевой, нам не нужно проверять текущий правый элемент ни с какими другими левыми элементами — они все дадут еще большую сумму. Мы сдвигаем правый указатель, тем самым вычеркивая из пространства поиска целый столбец вариантов. Одно сравнение исключает десятки, сотни или тысячи бесполезных проверок.

В зависимости от того, как именно движутся индексы, выделяют три основных паттерна.

Паттерн 1: Встречные указатели (Opposite Direction)

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

Один указатель ставится на начало структуры (left = 0), второй — на конец (right = len(arr) - 1). На каждом шаге цикла while left < right алгоритм принимает решение, какой из указателей сдвинуть навстречу другому.

Разберем реализацию задачи о поиске суммы (Two Sum II) на отсортированном массиве:

def two_sum_sorted(arr, target):
    left = 0
    right = len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            # Сумма слишком мала. Единственный способ её увеличить —
            # взять элемент большего значения слева.
            left += 1
        else:
            # Сумма слишком велика. Нужно взять элемент поменьше справа.
            right -= 1

    return [-1, -1] # Если пара не найдена

(Примечание: маркер виджета заменен для соответствия нумерации, правильный маркер ниже)

Логика движения строго детерминирована. Если current_sum < target, сдвиг right влево сделал бы сумму еще меньше (ведь массив отсортирован по возрастанию). Значит, единственный логичный шаг — сдвинуть left вправо.

Этот паттерн гарантирует, что каждый элемент массива будет прочитан не более одного раза. Указатели встретятся в середине, совершив в сумме ровно $N$ шагов. Временная сложность строго $O(N)$.

Где еще применяются встречные указатели

• Проверка на палиндром: left и right сравнивают символы с краев строки, двигаясь к центру. Если символы не совпадают — это не палиндром.
• Реверс массива in-place: left и right меняют местами элементы, на которые указывают, и делают шаг навстречу друг другу.
• Задача о контейнере с наибольшим количеством воды: указатели стоят по краям, и на каждом шаге сдвигается тот, который указывает на меньшую высоту стенки, в надежде найти стенку повыше.

Паттерн 2: Параллельные указатели (Same Direction / Fast and Slow)

В этом паттерне оба указателя начинают движение с одного конца массива (обычно с индекса 0) и движутся в одном направлении, но с разной скоростью или при разных условиях.

Чаще всего один указатель выступает в роли «разведчика» или «читателя» (fast), а второй — в роли «хранителя состояния» или «писателя» (slow). Этот подход незаменим для модификации массивов in-place (без выделения дополнительной памяти), когда удалять элементы через методы вроде .remove() или del слишком дорого из-за сдвига оставшихся элементов за $O(N)$.

Рассмотрим задачу: дан массив чисел. Нужно переместить все нули в конец массива, сохранив относительный порядок остальных элементов. Создавать новый массив нельзя.

Если использовать метод .pop() для нулей и .append(0) в конец, каждый .pop() из середины списка в Python потребует $O(N)$ времени на сдвиг элементов. В худшем случае (массив из одних нулей) сложность станет $O(N^2)$.

Решим это параллельными указателями:

def move_zeroes(arr):
    writer = 0 # Указывает на позицию, куда нужно записать следующее ненулевое число

    # reader бежит по всем элементам массива
    for reader in range(len(arr)):
        if arr[reader] != 0:
            # Нашли ненулевой элемент. Меняем его местами с элементом под writer
            arr[writer], arr[reader] = arr[reader], arr[writer]
            writer += 1

    return arr

Как это работает на концептуальном уровне:

1. Указатель reader (в коде это переменная цикла) безусловно проходит каждый элемент массива.
2. Указатель writer фиксирует границу обработанной части. Всё, что находится строго до индекса writer, гарантированно не является нулем.
3. Пространство между writer и reader — это зона, где скапливаются найденные нули.
4. Когда reader встречает ненулевое число, оно «перепрыгивает» через зону нулей на позицию writer, а первый ноль из этой зоны отправляется на место reader.

Сложность такого решения — $O(N)$ по времени (каждый элемент посещается один раз) и $O(1)$ по памяти.

Разновидности параллельных указателей

Параллельные указатели могут двигаться не только по одному массиву, но и по двум разным. Классический пример — слияние двух отсортированных массивов в один. Указатель i бежит по первому массиву, указатель j — по второму. На каждом шаге мы сравниваем arr1[i] и arr2[j], выбираем меньший элемент для итогового массива и сдвигаем только тот указатель, чей элемент был выбран.

Паттерн 3: Скользящее окно (Sliding Window)

Скользящее окно — это специализированная и более сложная форма параллельных указателей. Если в стандартных параллельных указателях нас интересуют сами элементы, на которые указывают индексы, то в скользящем окне нас интересует подмножество элементов между левым и правым указателями.

Окно имеет границы [left, right]. Правый указатель расширяет окно, добавляя новые элементы и меняя текущее состояние (например, увеличивая текущую сумму подмассива). Левый указатель сужает окно, когда текущее состояние нарушает заданное условие (например, сумма превысила лимит).

Этот паттерн настолько объемен и имеет столько нюансов при работе со строками и словарями, что требует отдельного глубокого изучения. Главное, что нужно зафиксировать сейчас: скользящее окно — это эволюция метода двух указателей, где индексы всегда движутся в одном направлении (вправо), никогда не возвращаясь назад, что и обеспечивает линейную сложность $O(N)$.

Границы применимости и подводные камни

Несмотря на эффективность, метод двух указателей — не серебряная пуля. Его применение жестко ограничено структурой данных и условиями задачи.

Зависимость от сортировки. Встречные указатели для поиска сумм или разностей работают только на отсортированных данных. Если массив не отсортирован, предварительная сортировка займет $O(N \log N)$ времени. В таком случае общая сложность алгоритма будет определяться сортировкой, а не проходом указателей. Если задача требует сохранить исходные индексы элементов (как в оригинальной задаче Two Sum на LeetCode), сортировка разрушит эти индексы, и метод двух указателей применять нельзя без дополнительных структур данных.

Поиск комбинаций, а не пар. Если задача требует найти три числа, дающих в сумме ноль (3Sum), два указателя сами по себе не справятся. Потребуется зафиксировать первое число внешним циклом, а для оставшейся части массива применить метод двух указателей. Сложность возрастет до $O(N^2)$, что, впрочем, все равно лучше наивного перебора за $O(N^3)$.

Ошибки сдвига (Infinite Loops). Самая частая ошибка при реализации — забыть сдвинуть указатель в одной из веток if/else, либо сдвинуть его не в ту сторону. Это приводит к бесконечному циклу. При написании кода всегда проверяйте инвариант: на каждой итерации цикла while расстояние между указателями должно сокращаться (для встречных) или хотя бы один указатель должен двигаться вперед (для параллельных).

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

Встречные указатели: поиск пар элементов и работа с отсортированными последовательностями

Если попросить разработчика найти в массиве три числа, дающих в сумме ноль, первой мыслью почти наверняка будет написать три вложенных цикла. Это даст абсолютно верный ответ, но потребует $O(N^3)$ времени. На массиве из нескольких тысяч элементов такой код «зависнет» на долгие секунды. Однако, если применить предварительную сортировку и грамотно расставить указатели, задачу можно решить за $O(N^2)$, сократив время выполнения в тысячи раз.

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

Симметрия и фильтрация: проверка палиндромов

Самое физически интуитивное применение встречных указателей — движение от краев к центру для проверки симметрии. Классическая задача на эту тему просит определить, является ли строка палиндромом, при этом игнорируя пробелы, знаки препинания и регистр символов.

В Python строку можно очистить, перевести в нижний регистр и сравнить с её перевернутой копией s == s[::-1]. Однако создание очищенной строки и её разворот требуют $O(N)$ дополнительной вспомогательной памяти. В условиях жестких ограничений (например, при парсинге гигантских текстовых логов) мы не можем позволить себе дублировать данные в оперативной памяти.

Встречные указатели позволяют решить задачу in-place, используя $O(1)$ памяти.

Логика работы:

1. Левый указатель left стартует с индекса $0$, правый right — с индекса $N - 1$.
2. Если символ под left не является буквой или цифрой, мы просто сдвигаем left вправо.
3. Аналогично, если символ под right — мусорный, сдвигаем right влево.
4. Когда оба указателя стоят на значащих символах, мы сравниваем их (приведя к одному регистру). Если они не равны — перед нами не палиндром.
5. Если равны, сдвигаем оба указателя навстречу друг другу.

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        # Пропускаем не-буквенно-цифровые символы слева
        while left < right and not s[left].isalnum():
            left += 1
        # Пропускаем не-буквенно-цифровые символы справа
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

Обратите внимание на условие left < right. Почему не left <= right? Если указатели встретились на одном и том же символе (строка нечетной длины), сравнивать символ с самим собой бессмысленно — это лишняя операция. В задачах на поиск пар или проверку симметрии строгое неравенство $<$ является стандартом.

Также критически важна проверка left < right внутри вложенных циклов while. Если строка состоит только из знаков препинания (например, ".,, ."), левый указатель без этого ограничителя улетел бы за пределы массива (IndexError), пытаясь найти букву.

Жадный выбор при сжатии границ: задача о контейнере

Паттерн встречных указателей раскрывает свою истинную мощь, когда движение указателя опирается на математическое доказательство. Легендарная задача «Container With Most Water» формулируется так: дан массив высот вертикальных линий. Нужно выбрать две линии, которые вместе с осью X образуют контейнер, вмещающий наибольшее количество воды.

Площадь контейнера зависит от двух факторов: расстояния между линиями (ширины) и высоты самой короткой из двух линий (вода перельется через край более низкой стенки). Формула площади: $Area = \min(h[left], h[right]) \times (right - left)$.

Наивный перебор всех пар линий занимает $O(N^2)$. Встречные указатели позволяют найти максимум за $O(N)$.

Мы ставим left на начало массива, а right на конец. Это дает нам контейнер максимально возможной ширины. Чтобы попытаться найти контейнер большей площади, нам нужно сдвинуть один из указателей. Но какой?

Здесь применяется жадный выбор. Допустим, $h[left] = 3$, а $h[right] = 8$. Текущая высота контейнера ограничена левой линией и равна $3$. Если мы сдвинем правый указатель (высокую линию) влево, ширина контейнера уменьшится. А что произойдет с высотой? Она либо останется равной $3$ (если новая правая линия будет выше $3$), либо станет еще меньше (если новая правая линия окажется ниже $3$).

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

Этот алгоритм гарантированно находит оптимум. На каждом шаге мы исключаем из рассмотрения ту линию, которая является «узким горлышком», отбрасывая все потенциальные пары с ней, так как мы уже проверили её в комбинации с максимально возможной шириной.

Сведение многомерных задач к линейным: 3Sum

Теперь вернемся к задаче, упомянутой в начале статьи: найти все уникальные тройки чисел в массиве, сумма которых равна нулю ($a + b + c = 0$).

Мы уже знаем, что задачу Two Sum II (поиск двух чисел с заданной суммой в отсортированном массиве) можно решить встречными указателями за $O(N)$. Идея решения 3Sum заключается в том, чтобы свести поиск тройки к серии поисков пар.

Алгоритм состоит из следующих шагов:

1. Сортировка массива. Это займет $O(N \log N)$. Сортировка необходима для применения встречных указателей и для легкого отсеивания дубликатов.
2. Фиксация первого элемента. Мы запускаем цикл for i in range(len(nums) - 2). Элемент nums[i] становится нашим $a$.
3. Поиск пары. Теперь нам нужно найти такие $b$ и $c$ в оставшейся части массива (от i + 1 до конца), чтобы $b + c = -a$. Это классическая задача Two Sum II, решаемая встречными указателями left и right.

Временная сложность такого подхода: внешний цикл выполняется $O(N)$ раз. Внутри него указатели пробегают оставшуюся часть массива за $O(N)$. Итого $O(N \times N) = O(N^2)$. Сортировка $O(N \log N)$ поглощается более медленным квадратичным компонентом.

Проблема дубликатов

Главная сложность алгоритмических секций в Яндексе при решении 3Sum — требование вернуть уникальные тройки. Если входной массив [-2, 0, 0, 2, 2], алгоритм не должен дважды выдать [-2, 0, 2].

Использование хеш-множеств (Set) для хранения найденных троек увеличит потребление памяти и замедлит работу алгоритма константными издержками на хеширование. Правильный подход — алгоритмический пропуск дубликатов на этапе движения указателей.

Дубликаты нужно отсекать на двух уровнях:

Уровень 1: Пропуск одинаковых фиксированных элементов ($a$) Если nums[i] == nums[i-1], это значит, что мы уже искали все возможные пары для этого числа на предыдущей итерации внешнего цикла. Мы должны пропустить этот шаг с помощью continue.

Уровень 2: Пропуск одинаковых элементов в паре ($b$ и $c$) Когда мы нашли успешную тройку (сумма равна нулю), мы записываем её в ответ. После этого нам нужно сдвинуть left вправо, а right влево, чтобы продолжить поиск других пар для текущего $a$. Но если следующий элемент nums[left] такой же, как предыдущий, мы снова получим ту же самую тройку. Поэтому после успешного нахождения пары мы обязаны «промотать» указатели через все повторяющиеся значения.

Код, реализующий эту логику:

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Уровень 1: пропускаем дубликаты для первого числа
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1
        target = -nums[i]

        while left < right:
            current_sum = nums[left] + nums[right]

            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])

                # Уровень 2: пропускаем дубликаты для второго и третьего чисел
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                # Сдвигаем указатели на новые уникальные значения
                left += 1
                right -= 1

            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result

Заметьте, что внутри циклов пропуска дубликатов while left < right and nums[left] == nums[left + 1] мы снова используем проверку left < right. Без неё, в массиве состоящем из одних нулей [0, 0, 0, 0, 0], левый указатель мог бы выйти за пределы массива или пересечься с правым.

Слияние с концов: квадраты отсортированного массива

До сих пор мы рассматривали задачи, где указатели двигались навстречу друг другу для поиска чего-либо в существующем массиве. Но встречные указатели также эффективны для построения новых структур данных на основе анализа концов массива.

Рассмотрим задачу «Квадраты отсортированного массива». Дан массив целых чисел, отсортированный по неубыванию. Нужно вернуть массив квадратов этих чисел, также отсортированный по неубыванию. Пример ввода: [-4, -1, 0, 3, 10]. Ожидаемый вывод: [0, 1, 9, 16, 100].

Очевидное решение — возвести все элементы в квадрат и затем отсортировать массив встроенной функцией. Сложность такого подхода составит $O(N \log N)$. Но мы можем сделать это за $O(N)$.

Ключевой инсайт: исходный массив уже отсортирован. Это значит, что самые большие по модулю числа (а значит, и самые большие квадраты) находятся либо в самом начале массива (большие отрицательные числа), либо в самом конце (большие положительные числа). Наименьшие квадраты будут где-то в середине, ближе к нулю.

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

В этой задаче условие цикла должно быть while left <= right. Знак равенства $=$ здесь обязателен. Если использовать строгое неравенство $<$, алгоритм остановится, когда указатели встретятся на последнем оставшемся элементе (например, на нуле в нашем примере), и этот элемент не будет добавлен в результирующий массив. Когда мы строим новый массив из всех элементов старого, мы обязаны обработать каждый элемент, включая тот, на котором указатели сошлись.

def sorted_squares(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1

    # Индекс для записи в результирующий массив с конца
    write_pointer = n - 1

    while left <= right:
        left_square = nums[left] ** 2
        right_square = nums[right] ** 2

        if left_square > right_square:
            result[write_pointer] = left_square
            left += 1
        else:
            result[write_pointer] = right_square
            right -= 1

        write_pointer -= 1

    return result

Вспомогательная память (auxiliary space) этого алгоритма равна $O(N)$, так как мы создаем новый массив result того же размера, что и входной. Избежать выделения памяти в этой задаче невозможно, так как перезапись элементов in-place разрушила бы исходные данные, которые еще предстоит проанализировать.

Резюме нюансов работы с границами

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

1. Какое условие остановки? Если вы ищете пару или проверяете симметрию — используйте left < right. Если вы обрабатываете каждый элемент и строите новую структуру — используйте left <= right.
2. Защищены ли вложенные циклы? Любой внутренний цикл while, который сдвигает указатель (например, для пропуска дубликатов или мусорных символов), должен дублировать проверку left < right. Иначе гарантирован выход за границы массива.
3. Движутся ли указатели при любом исходе? Частая ошибка новичков — забыть сдвинуть указатели в блоке if/else, что приводит к бесконечному циклу. На каждой итерации основного цикла while хотя бы один из указателей должен изменить свое значение.

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

Параллельные указатели: слияние массивов и эффективное удаление дубликатов in-place

Представьте, что у вас есть отсортированный массив из десяти миллионов идентификаторов пользователей, и вам нужно очистить его от дубликатов. Использование структуры данных set потребует выделения памяти еще под десять миллионов элементов, что может привести к нехватке оперативной памяти (Out of Memory). Использование встроенных методов удаления элементов списка прямо в цикле обрушит производительность и заставит алгоритм работать часами вместо миллисекунд. Решение этой инженерной проблемы кроется в концепции in-place модификации с помощью параллельных указателей.

Проблема скрытой квадратичной сложности

В языках программирования высокого уровня, таких как Python, списки (lists) реализованы как динамические массивы. Под капотом (в реализации CPython) это непрерывный блок памяти, хранящий ссылки на объекты. Такая структура обеспечивает мгновенный доступ к любому элементу по индексу за $O(1)$. Но у непрерывности есть цена.

Когда вы вызываете метод .pop(i), .remove(val) или используете оператор del arr[i] для удаления элемента из середины или начала массива, образуется «дыра». Чтобы сохранить непрерывность массива, интерпретатор вынужден сдвинуть все элементы, находящиеся правее удаленного, на одну позицию влево.

Если массив состоит из $N$ элементов, то удаление нулевого элемента потребует сдвига $N-1$ элементов. Это операция со сложностью $O(N)$. Если мы пишем цикл, который проходит по массиву и удаляет дубликаты с помощью встроенных методов, мы помещаем операцию $O(N)$ внутрь цикла $O(N)$. В результате алгоритм деградирует до временной сложности $O(N^2)$.

Чтобы остаться в рамках линейного времени $O(N)$ и при этом не выделять $O(N)$ дополнительной памяти под новый массив (то есть достичь пространственной сложности $O(1)$), нам необходимо отказаться от физического удаления элементов на каждом шаге. Вместо этого мы будем перезаписывать массив поверх самого себя.

Паттерн «Читатель и Писатель» (Fast and Slow Pointers)

Когда указатели движутся навстречу друг другу, они обычно ищут пару элементов, удовлетворяющую условию. Когда указатели движутся в одном направлении (параллельно), они выполняют разные роли. Этот паттерн часто называют Fast and Slow pointers, но для задач модификации in-place гораздо точнее метафора «Читатель и Писатель».

1. Быстрый указатель (Читатель / fast): Его задача — сканировать массив элемент за элементом, нигде не задерживаясь. Он ищет полезные данные, которые должны остаться в итоговом массиве.
2. Медленный указатель (Писатель / slow): Его задача — указывать на позицию, куда нужно записать следующие полезные данные, найденные Читателем.

Писатель всегда отстает от Читателя или идет вровень с ним. Благодаря этому Писатель никогда не затирает данные, которые Читатель еще не успел проанализировать.

Классическая задача: Удаление дубликатов (LeetCode 26)

Рассмотрим отсортированный массив nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]. Наша цель — изменить массив так, чтобы в его начале оказались уникальные элементы в строгом порядке, а что останется в конце массива — не имеет значения. Функция должна вернуть количество уникальных элементов.

Поскольку массив отсортирован, все дубликаты гарантированно сгруппированы вместе. Нам не нужно помнить элементы, которые мы видели давно — достаточно сравнивать текущий элемент с предыдущим записанным.

Алгоритм строится следующим образом:

1. Если массив пуст, возвращаем 0.
2. Первый элемент массива nums[0] всегда уникален в рамках просмотренной части, поэтому Писатель (slow) начинает работу с индекса 1 (это место для записи второго уникального элемента).
3. Читатель (fast) также начинает с индекса 1 и идет до конца массива.
4. На каждом шаге Читатель сравнивает текущий элемент nums[fast] с последним уникальным элементом, который мы сохранили. Последний сохраненный элемент всегда находится на позиции slow - 1.
5. Если nums[fast] == nums[slow - 1], это дубликат. Читатель просто идет дальше.
6. Если nums[fast] != nums[slow - 1], Читатель нашел новый уникальный элемент. Мы записываем его на позицию Писателя: nums[slow] = nums[fast], после чего Писатель делает шаг вперед (slow += 1), резервируя место для следующей находки.

Реализация на Python:

def removeDuplicates(nums: list[int]) -> int:
    if not nums:
        return 0

    slow = 1  # Писатель ждет на индексе 1

    for fast in range(1, len(nums)):
        # Сравниваем текущий элемент с последним записанным уникальным
        if nums[fast] != nums[slow - 1]:
            nums[slow] = nums[fast]
            slow += 1

    return slow  # slow совпадает с количеством уникальных элементов

Временная сложность этого решения — строго $O(N)$, так как цикл for проходит по массиву ровно один раз. Пространственная сложность — $O(1)$, так как мы используем только две целочисленные переменные, независимо от объема данных.

Эволюция паттерна: Допуск определенного числа дубликатов (LeetCode 80)

Сила паттерна «Читатель и Писатель» раскрывается при усложнении логики. Что, если бизнес-требование изменилось: теперь нам нужно оставить в массиве дубликаты, но не более двух одинаковых элементов подряд?

Если пытаться решать эту задачу через подсчет вхождений в словаре или через удаление элементов срезами, код быстро станет запутанным и неэффективным. Но с параллельными указателями решение меняется ровно на один символ.

Давайте рассуждать. Писатель (slow) по-прежнему указывает на место, куда мы запишем следующий разрешенный элемент. Читатель (fast) находит кандидата. Как понять, можно ли записать кандидата nums[fast]? Кандидата нельзя записывать только в одном случае: если он создаст тройку одинаковых элементов. Поскольку массив отсортирован, тройка образуется тогда и только тогда, когда новый элемент равен элементу, который был записан две позиции назад (то есть на позиции slow - 2).

Алгоритм:

1. Первые два элемента массива всегда допустимы (даже если они одинаковые, это максимум пара). Поэтому Писатель и Читатель начинают с индекса 2.
2. Читатель проверяет: если nums[fast] != nums[slow - 2], значит, добавление nums[fast] безопасно, оно не создаст третью копию.
3. Копируем элемент и сдвигаем Писателя.

def removeDuplicatesTwice(nums: list[int]) -> int:
    if len(nums) <= 2:
        return len(nums)

    slow = 2
    for fast in range(2, len(nums)):
        if nums[fast] != nums[slow - 2]:
            nums[slow] = nums[fast]
            slow += 1

    return slow

Этот элегантный подход масштабируется на любое допустимое количество копий $K$. Достаточно начинать с индекса $K$ и сравнивать nums[fast] с nums[slow - K].

Обратные параллельные указатели: Слияние массивов

До сих пор мы рассматривали указатели, которые двигались слева направо (от начала к концу массива). Однако существует класс задач, где движение слева направо при in-place модификации неизбежно приводит к потере данных. Самый яркий пример — слияние двух отсортированных массивов.

В задаче LeetCode 88 даны два отсортированных целочисленных массива nums1 и nums2. Массив nums1 имеет размер $m + n$, где первые $m$ элементов — это реальные числа, а последние $n$ элементов — нули, зарезервированные под элементы массива nums2 (размер которого равен $n$). Требуется слить nums2 в nums1 так, чтобы итоговый массив остался отсортированным.

Ловушка прямого прохода

Интуитивный подход — поставить указатель p1 на начало nums1, указатель p2 на начало nums2, и сравнивать их, записывая меньший элемент. Но куда записывать? Если мы начнем писать прямо в nums1 с индекса 0, мы можем перетереть полезные данные.

Пример: nums1 = [4, 5, 6, 0, 0, 0] ($m=3$), nums2 = [1, 2, 3] ($n=3$). Сравниваем 4 и 1. Единица меньше. Пишем 1 в nums1[0]. Теперь nums1 = [1, 5, 6, 0, 0, 0]. Мы навсегда потеряли число 4.

Чтобы избежать этого при обходе слева направо, нам пришлось бы создать копию первых $m$ элементов nums1, что потребует $O(M)$ дополнительной памяти, нарушая требование in-place.

Решение: Слияние с конца

Ключ к решению кроется в структуре nums1. Пустое место (нули) находится в конце массива. Если мы начнем заполнять массив с конца, записывая туда самые большие элементы, мы никогда не перетрем неизученные данные, потому что будем писать в пустые слоты.

Здесь нам понадобятся три указателя, все они движутся справа налево (параллельно друг другу в обратном направлении):

• p1 указывает на последний значащий элемент в nums1 (индекс $m - 1$).
• p2 указывает на последний элемент в nums2 (индекс $n - 1$).
• p (наш Писатель) указывает на самую последнюю ячейку в nums1 (индекс $m + n - 1$).

На каждом шаге мы сравниваем nums1[p1] и nums2[p2]. Тот элемент, который больше, отправляется на позицию p, после чего соответствующий указатель чтения (p1 или p2) и указатель записи p сдвигаются на шаг влево.

Реализация алгоритма:

def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1

    # Пока есть элементы в обоих массивах
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # Обработка оставшихся элементов
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

Разбор граничных случаев (Edge Cases)

В коде выше есть второй цикл while p2 >= 0. Почему он необходим и почему нет симметричного цикла while p1 >= 0? Это один из самых частых вопросов на алгоритмических секциях.

Рассмотрим два сценария завершения первого цикла:

Сценарий А: nums1 исчерпан раньше, чем nums2 Например, nums1 = [4, 5, 6, 0, 0, 0], nums2 = [1, 2, 3]. Мы быстро перенесем 6, 5 и 4 в конец nums1. Указатель p1 станет равен -1. Первый цикл прервется. Но в nums2 еще остались элементы (1, 2, 3), а в начале nums1 остались нетронутые ячейки. В этом случае мы обязаны перенести остатки nums2 в nums1. Именно это и делает второй цикл.

Сценарий Б: nums2 исчерпан раньше, чем nums1 Например, nums1 = [1, 2, 3, 0, 0, 0], nums2 = [4, 5, 6]. Мы перенесем 6, 5 и 4 в конец nums1. Указатель p2 станет равен -1. Первый цикл прервется. В nums1 остались элементы 1, 2, 3, а указатель p1 указывает на индекс 2. Нужно ли их куда-то перемещать? Нет. Они уже находятся на своих правильных местах в целевом массиве nums1. Поэтому цикл while p1 >= 0 алгоритмически избыточен.

Понимание этой асимметрии демонстрирует глубокое осознание того, как работает память при in-place модификациях.

Параллельные указатели — это инструмент управления потоком данных внутри одной структуры. Отвязывая скорость «чтения» от скорости «записи» или меняя направление обхода на противоположное, мы можем перестраивать массивы без дополнительных затрат памяти, избегая при этом катастрофических просадок производительности, связанных с системными сдвигами элементов.

Фундамент скользящего окна: концепция фиксированного размера для анализа локальных подмножеств

Представьте, что вы анализируете графики температуры и вам нужно найти неделю с самой высокой средней температурой за прошедший год. Если для каждого из 365 дней вы будете заново складывать показатели за следующие семь суток, вы совершите множество лишних действий. Завтрашняя неделя отличается от сегодняшней ровно на два дня: один день ушел в прошлое, один добавился в будущем. Остальные пять дней между ними абсолютно идентичны. Зачем складывать их заново? Этот простой жизненный принцип лежит в основе одного из самых мощных алгоритмических паттернов — скользящего окна.

В предыдущих материалах мы разобрали, как два указателя помогают двигаться по массиву навстречу друг другу или в одном направлении, отбрасывая заведомо неверные варианты. Скользящее окно — это эволюция параллельных указателей. Здесь два указателя жестко связаны друг с другом расстоянием (размером окна) или логическим условием, образуя непрерывную область видимости, которая «скользит» по структуре данных.

Анатомия избыточных вычислений

Чтобы понять ценность паттерна, необходимо увидеть скрытую квадратичную сложность в задачах на поиск подмассивов. Рассмотрим классическую формулировку: дан массив целых чисел и число $K$. Необходимо найти максимальную сумму подмассива длиной ровно $K$.

Наивный подход заставляет нас проверять каждый возможный старт подмассива и запускать внутренний цикл для суммирования $K$ элементов.

def max_sum_naive(arr, k):
    if not arr or k > len(arr):
        return 0

    max_sum = float('-inf')
    # Внешний цикл определяет начало подмассива
    for i in range(len(arr) - k + 1):
        current_sum = 0
        # Внутренний цикл суммирует K элементов
        for j in range(i, i + k):
            current_sum += arr[j]
        max_sum = max(max_sum, current_sum)

    return max_sum

С точки зрения асимптотического анализа, внешний цикл выполняется $N - K + 1$ раз, где $N$ — длина массива. Внутренний цикл всегда делает ровно $K$ итераций. Итоговая временная сложность составляет $O((N - K) \cdot K)$. В худшем случае, когда $K$ равно половине длины массива ($K = N / 2$), сложность деградирует до $O(N^2)$.

Проблема кроется в многократном чтении одних и тех же данных. Если $K = 5$, то элемент с индексом $3$ будет прочитан пять раз: когда он является пятым элементом окна, четвертым, третьим, вторым и первым. Алгоритм не сохраняет состояние между итерациями внешнего цикла, полностью уничтожая накопленную информацию о сумме.

Механика фиксированного окна

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

Алгоритм всегда разделяется на две логические фазы:

1. Инициализация (Bootstrapping): первоначальное заполнение окна. Мы вычисляем состояние для первых $K$ элементов массива.
2. Скольжение (Sliding): проход по оставшейся части массива. На каждом шаге окно сдвигается на одну позицию вправо. Состояние обновляется за константное время $O(1)$.

Перепишем задачу поиска максимальной суммы с использованием этого паттерна:

def max_sum_sliding_window(arr, k):
    if not arr or k > len(arr):
        return 0

    # Фаза 1: Инициализация первого окна
    current_sum = sum(arr[:k])
    max_sum = current_sum

    # Фаза 2: Скольжение окна
    for i in range(k, len(arr)):
        # Добавляем элемент, вошедший в окно (справа)
        # и вычитаем элемент, вышедший из окна (слева)
        current_sum = current_sum + arr[i] - arr[i - k]
        max_sum = max(max_sum, current_sum)

    return max_sum

Временная сложность этого решения — строго $O(N)$. Инициализация занимает $O(K)$ операций, а цикл скольжения проходит оставшиеся $N - K$ элементов, выполняя внутри базовые арифметические действия за $O(1)$. В сумме получаем $O(K + N - K) = O(N)$. Вспомогательная память остается $O(1)$, так как мы храним только две числовые переменные, независимо от размеров $N$ и $K$.

Математика индексов

Главная сложность при реализации фиксированного окна на практике — ошибка на единицу (off-by-one error) при вычислении индексов. Разберем механику цикла for i in range(k, len(arr)) детально.

В момент старта фазы скольжения наше окно уже покрывает индексы от $0$ до $K - 1$ включительно. Следовательно, первый элемент, который должен попасть в окно при сдвиге, находится по индексу $K$. Именно поэтому цикл начинается с k.

Переменная i в нашем цикле выполняет роль «правого указателя». Она указывает на элемент, который прямо сейчас входит в окно. Если текущий элемент имеет индекс $i$, а размер окна равен $K$, какой индекс у элемента, который должен покинуть окно?

Поскольку окно сдвигается на один шаг, его левая граница тоже смещается. Элемент, который мы должны вычесть, остался ровно на $K$ позиций позади текущего правого указателя. Его индекс всегда равен $i - K$.

Проверим на примере: $K = 3$.

• Инициализация забрала индексы $0, 1, 2$.
• Первая итерация цикла: i = 3. Добавляем arr[3]. Вычитаем arr[3 - 3] = arr[0]. Новое окно содержит индексы $1, 2, 3$. Размер окна: $3 - 1 + 1 = 3$. Все верно.

Поддержание нечислового состояния

Сумма — простейший вид состояния окна. Однако паттерн фиксированного окна применим к любым задачам, где состояние можно инкрементально обновлять. Рассмотрим задачу на работу со строками: найти максимальное количество гласных букв в подстроке длины $K$.

Здесь состояние окна — это не сумма самих элементов, а счетчик элементов, удовлетворяющих определенному условию.

def max_vowels(s: str, k: int) -> int:
    vowels = set('aeiou')

    # Фаза 1: Инициализация
    current_vowels = 0
    for i in range(k):
        if s[i] in vowels:
            current_vowels += 1

    max_vowels_count = current_vowels

    # Фаза 2: Скольжение
    for i in range(k, len(s)):
        # Если входящий элемент - гласная, увеличиваем счетчик
        if s[i] in vowels:
            current_vowels += 1

        # Если выходящий элемент - гласная, уменьшаем счетчик
        if s[i - k] in vowels:
            current_vowels -= 1

        max_vowels_count = max(max_vowels_count, current_vowels)

    return max_vowels_count

Логика обновления состояния current_vowels опирается на тот же принцип вытеснения. Мы проверяем свойства элемента s[i] (вошедшего) и s[i - k] (вышедшего). Если строка состоит из миллионов символов, этот алгоритм отработает за один проход, сохраняя $O(N)$ времени и $O(1)$ дополнительной памяти (множество vowels имеет фиксированный размер из 5 элементов).

Границы применимости и проблема необратимости

Паттерн фиксированного скользящего окна выглядит универсальным инструментом для любых подмассивов длины $K$. Однако его эффективность критически зависит от одного математического свойства обновляемого состояния — обратимости операции.

В разобранных примерах состояние легко корректировалось при удалении левого элемента:

• Для суммы: операция сложения обратима вычитанием (sum -= arr[i - k]).
• Для счетчика: инкремент обратим декрементом (count -= 1).
• Для произведения (если нет нулей): умножение обратимо делением (prod /= arr[i - k]).

Но что произойдет, если нас попросят найти максимальный элемент в каждом окне размера $K$?

Добавление нового элемента справа обрабатывается легко: мы просто сравниваем текущий максимум с новым элементом. Но когда окно сдвигается, и элемент arr[i - k] покидает его, возникает проблема. Если этот ушедший элемент был текущим максимумом всего окна, мы не можем за $O(1)$ узнать, кто теперь стал новым максимумом. Нам придется заново сканировать оставшиеся $K - 1$ элементов, что возвращает нас к квадратичной сложности $O(N \cdot K)$.

Операция поиска максимума (или минимума) необратима. Нельзя просто «вычесть» старый максимум из состояния. Для решения таких задач базового скользящего окна недостаточно — требуются дополнительные структуры данных, такие как монотонная очередь или дерево отрезков, которые позволяют поддерживать актуальный экстремум при удалении элементов.

Еще один подводный камень — наличие нулей при вычислении произведения в окне. Если элемент arr[i - k], покидающий окно, равен нулю, мы не можем выполнить операцию prod /= 0. Более того, если внутри окна есть ноль, текущее произведение равно нулю, и при выходе этого нуля из окна мы не знаем, каким было произведение остальных чисел. В таких случаях состояние окна приходится сбрасывать и пересчитывать, либо поддерживать счетчик нулей внутри окна как отдельную переменную состояния.

Структурный шаблон кода

Независимо от сложности бизнес-логики, код фиксированного скользящего окна всегда укладывается в жесткий шаблон. Понимание этого каркаса позволяет писать алгоритм без ошибок в индексах на любом собеседовании.

1. Защита от граничных случаев (Guard Clauses): Проверка длины массива. Если $K > N$, окно сформировать невозможно.
2. Начальное состояние: Аккумулятор для текущего окна и переменная для хранения глобального ответа (максимума, минимума).
3. Первичный цикл for i in range(k): Наполнение аккумулятора первыми $K$ элементами.
4. Фиксация первого ответа: Копирование значения аккумулятора в глобальный ответ.
5. Вторичный цикл for i in range(k, n):
   • Изменение аккумулятора с учетом arr[i].
   • Изменение аккумулятора с учетом arr[i - k].
   • Обновление глобального ответа.

Разделение на два цикла (инициализация и скольжение) делает код чище и избавляет от необходимости писать внутри одного большого цикла громоздкие проверки вида if i >= k: .... Чистый код без лишних ветвлений внутри цикла выполняется быстрее и легче читается.

Фиксированное окно — это первый шаг к пониманию того, как алгоритмы могут сохранять и переиспользовать промежуточные результаты. Осознав механику добавления и удаления элементов по краям, можно переходить к более сложным сценариям, где размер окна не задан жестко, а динамически расширяется и сужается в зависимости от свойств самих данных.

Классическое скользящее окно фиксированного размера отлично справляется с задачами, где длина искомой последовательности известна заранее. Но алгоритмическая реальность чаще ставит иные условия: найти подмассив с суммой не менее $S$, или подстроку без повторяющихся символов. Длина ответа неизвестна. Использование окна фиксированного размера здесь потребовало бы перебора всех возможных длин от $1$ до $N$, что неминуемо возвращает нас к квадратичной или кубической сложности.

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

Архитектура динамического окна

В основе паттерна лежат два указателя, которые всегда движутся слева направо. Указатель right отвечает за расширение окна и добавление новых элементов в текущее состояние. Указатель left отвечает за сужение окна и удаление элементов из состояния.

Ключевой концепт, управляющий движением — валидность состояния окна. Окно считается валидным, если элементы внутри него удовлетворяют условию задачи (например, «сумма элементов больше $10$» или «в окне нет дубликатов»). В зависимости от того, что именно мы ищем — самую длинную или самую короткую последовательность — реакция на валидность меняется на противоположную.

Существует два фундаментальных подтипа динамического окна, которые покрывают подавляющее большинство задач LeetCode Medium на эту тему.

Паттерн 1: Поиск наибольшей длины (Longest)

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

Логика работы:

1. Мы расширяем окно, сдвигая right и добавляя элемент.
2. Если добавление элемента сделало окно невалидным (нарушило условие), мы обязаны сужать окно, сдвигая left, до тех пор, пока окно снова не станет валидным.
3. Как только окно гарантированно валидно, мы обновляем максимальную найденную длину.

Классический пример — задача поиска длины самой длинной подстроки без повторяющихся символов (Longest Substring Without Repeating Characters).

Условие валидности здесь: все символы в окне должны быть уникальными. Для отслеживания состояния используем структуру данных set, которая позволяет за $O(1)$ проверять наличие символа.

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        # Если символ уже есть в окне, состояние НЕВАЛИДНО.
        # Сужаем окно слева, пока дубликат не будет удален.
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        # Теперь окно точно ВАЛИДНО.
        # Добавляем новый символ и обновляем рекорд.
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

Разберем механику на строке "abcabcbb". Указатель right последовательно добавляет 'a', 'b', 'c'. Окно валидно, max_len становится равным $3$. На следующем шаге right указывает на вторую 'a'. Символ 'a' уже есть в char_set. Окно стало невалидным. Внутренний цикл while начинает работу: он удаляет символ под указателем left (это первая 'a') из множества и сдвигает left на один шаг вправо. Теперь в окне "bca", дубликатов нет, цикл while завершается. Мы добавляем новую 'a' в множество и продолжаем работу.

Критически важный нюанс этого паттерна — расположение строки max_len = max(...). Она находится строго вне внутреннего цикла while. При поиске максимума внутренний цикл выполняет роль «ремонтной бригады»: он чинит сломанное (невалидное) состояние. Замерять длину окна имеет смысл только после того, как ремонт окончен и окно снова соответствует правилам задачи.

Паттерн 2: Поиск наименьшей длины (Shortest)

Логика кардинально меняется, когда нужно найти кратчайшую последовательность. Здесь мы расширяем окно до тех пор, пока оно не станет валидным. Как только условие выполнилось, мы пытаемся его оптимизировать (сделать окно короче), сдвигая left, пока окно остается валидным.

Пример — задача Minimum Size Subarray Sum. Дан массив положительных чисел и целевое значение $target$. Нужно найти минимальную длину непрерывного подмассива, сумма элементов которого больше или равна $target$.

Условие валидности: текущая сумма окна $\geq target$.

def min_sub_array_len(target: int, nums: list[int]) -> int:
    left = 0
    current_sum = 0
    min_len = float('inf')

    for right in range(len(nums)):
        current_sum += nums[right]

        # Пока окно ВАЛИДНО, пытаемся его улучшить (сузить)
        while current_sum >= target:
            # Обновляем рекорд, так как текущее окно валидно
            min_len = min(min_len, right - left + 1)

            # Сужаем окно, вычитая левый элемент
            current_sum -= nums[left]
            left += 1

    return min_len if min_len != float('inf') else 0

Рассмотрим массив [2, 3, 1, 2, 4, 3] и $target = 7$. Указатель right суммирует элементы: $2 + 3 + 1 = 6$. Окно невалидно. Сдвигаем right дальше, добавляем $2$. Сумма $8$. Окно стало валидным ($8 \geq 7$). Мы заходим во внутренний цикл while. Сразу фиксируем текущую длину окна — $4$. Затем пытаемся отбросить левый элемент (двойку). Сумма становится $8 - 2 = 6$. Условие $6 \geq 7$ ложно. Цикл while прерывается. Дальше right добавляет $4$. Сумма $6 + 4 = 10$. Окно снова валидно. Заходим в while. Фиксируем длину $4$. Отбрасываем левый элемент ($3$). Сумма $7$. Условие $7 \geq 7$ истинно! Мы остаемся в цикле while, фиксируем новую минимальную длину $3$, отбрасываем левый элемент ($1$). Сумма становится $6$, цикл прерывается.

В этом паттерне обновление рекорда min_len = min(...) находится строго внутри цикла while. Внутренний цикл здесь — это не ремонт, а фаза сбора урожая. Мы заходим в него только тогда, когда окно валидно, и на каждом шаге сужения проверяем, не нашли ли мы еще более короткий валидный вариант.

Асимптотическая сложность: почему это линейное время

Конструкция while внутри for часто вызывает у начинающих разработчиков ассоциацию с квадратичной сложностью $O(N^2)$. Чтобы понять, почему динамическое скользящее окно работает за $O(N)$, применим метод амортизационного анализа.

Посмотрим на жизненный цикл любого элемента массива в контексте наших указателей. Указатель right начинает с индекса $0$ и доходит до конца массива. Каждый элемент добавляется в окно ровно один раз. Это $N$ операций. Указатель left также начинает с индекса $0$ и движется только вправо. Он никогда не возвращается назад. Следовательно, каждый элемент может быть удален из окна максимум один раз. Это еще $N$ операций.

Даже если в какой-то момент внутренний цикл while выполнится $10$ раз подряд, это означает лишь то, что указатель left догнал right, удалив $10$ элементов. За весь проход по массиву внутренний цикл суммарно не сможет сделать больше $N$ итераций. Общее количество базовых операций ограничено константой, умноженной на $N$ (добавление + удаление), что дает итоговую временную сложность $O(N)$. Пространственная сложность зависит от хранимого состояния: $O(1)$ для суммы и $O(K)$, где $K$ — размер алфавита, для хранения уникальных символов в set.

Ограничения паттерна: требование монотонности

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

Вернемся к задаче Minimum Size Subarray Sum. В условии было сказано: «Дан массив положительных чисел». Что произойдет, если в массиве появятся отрицательные числа?

Пусть задан массив [3, -2, 5] и $target = 4$.

1. right указывает на $3$. Сумма $3$. Окно невалидно.
2. right указывает на $-2$. Сумма $1$. Окно невалидно.
3. right указывает на $5$. Сумма $6$. Окно валидно ($6 \geq 4$).

Мы заходим в цикл while, фиксируем длину $3$ (подмассив [3, -2, 5]) и сужаем окно, отбрасывая $3$. Текущая сумма становится $6 - 3 = 3$. Окно невалидно, цикл завершается. Ответ алгоритма — $3$.

Но правильный ответ — $1$ (подмассив [5], сумма которого $5 \geq 4$). Почему алгоритм пропустил этот ответ?

Логика скользящего окна строится на аксиоме: если добавление элементов делает сумму больше, то удаление элементов делает ее меньше. Когда мы встретили отрицательное число $-2$, сумма упала. Указатель right продолжал двигаться, надеясь найти числа, которые вытянут сумму вверх. Но из-за того, что на старте мы накопили отрицательный «балласт», при сужении окна отбрасывание положительной тройки опустило сумму ниже таргета, хотя внутри окна скрывался идеальный ответ.

Наличие отрицательных чисел разрушает монотонность. Мы больше не можем гарантировать, что сужение окна слева приближает нас к границе невалидности, а расширение справа всегда отдаляет от нее. Для задач с отрицательными числами и поиском суммы динамическое окно неприменимо — там используются префиксные суммы в комбинации с хеш-таблицами или монотонными очередями.

Граничные случаи и инициализация

При реализации паттерна важно правильно обрабатывать начальные значения и пустые вводы.

Для поиска максимума переменная max_len инициализируется нулем. Если валидных подстрок нет (например, массив пуст), алгоритм корректно вернет $0$. Важно следить за тем, чтобы не инициализировать max_len отрицательным числом, так как длина не может быть меньше нуля.

Для поиска минимума переменная min_len должна инициализироваться значением, которое гарантированно больше любой возможной длины подмассива. В Python для этого идеально подходит float('inf'). В языках со строгой типизацией используют MAX_INT или длину массива плюс один (len(nums) + 1). Если после завершения цикла min_len осталась равна float('inf'), это означает, что условие ни разу не было выполнено, и нужно вернуть $0$ или иное значение, требуемое задачей. Прямой возврат min_len в таком случае приведет к ошибке.

Еще один нюанс — пересечение указателей. В классических задачах на динамическое окно явная проверка left <= right во внутреннем цикле требуется редко. Если логика обновления состояния (например, суммы) реализована верно, left никогда не обгонит right. Например, если мы ищем сумму $\geq target$, и $target > 0$, то при left == right сумма окна равна одному элементу. Если мы вычтем его, сумма станет $0$, условие $0 \geq target$ станет ложным, и цикл while безопасно завершится до того, как left станет больше right. Однако при работе со сложными кастомными условиями валидности добавление left <= right во внутренний цикл служит хорошей страховкой от выхода за границы текущего окна.

Освоение динамического скользящего окна сводится к умению четко сформулировать, что является «валидным состоянием» для конкретной задачи, и применить один из двух базовых шаблонов, разместив обновление результата с правильной стороны от цикла сужения.

Синтаксис скользящего окна выглядит обманчиво просто: два указателя, один внешний цикл for или while для расширения, один внутренний while для сужения. Структурно алгоритм гарантирует, что каждый элемент будет добавлен в окно один раз и удален не более одного раза, что обещает линейную сложность $O(N)$. Однако на практике решения с идеальной структурой указателей часто получают вердикт Time Limit Exceeded (TLE). Причина кроется не в движении границ, а в том, как именно алгоритм отвечает на вопрос: «Является ли текущее окно валидным?».

Если проверка условия требует перебора элементов внутри текущего окна, сложность незаметно деградирует. Оптимизация этого узкого места требует отказа от пересчета данных в пользу поддержания непрерывного состояния с помощью вспомогательных переменных.

Иллюзия константного времени и цена валидации

В динамическом скользящем окне границы определяются логическим условием. Например, окно валидно, если сумма его элементов не превышает $S$, или если в нем нет дубликатов.

Наивный подход предполагает вычисление этого условия на каждом шаге заново:

# Антипаттерн: скрытая сложность O(N * K)
left = 0
for right in range(len(arr)):
    # Срез arr[left:right+1] создает новый список за O(K)
    # sum() итерируется по нему за O(K)
    while sum(arr[left:right+1]) > target:
        left += 1

Даже если отказаться от срезов и итерироваться по индексам от left до right, операция проверки занимает время, пропорциональное текущей длине окна $K$. В худшем случае, когда окно охватывает почти весь массив, алгоритм совершает серию проверок длиной $1, 2, 3 \dots N$, что приводит к квадратичной сложности $O(N^2)$.

Чтобы сохранить амортизированную сложность $O(N)$, проверка условия должна выполняться строго за $O(1)$. Это достигается принципом дельта-обновления: мы не вычисляем состояние окна с нуля, а корректируем его, учитывая только ту «дельту» (разницу), которую вносит один входящий или один выходящий элемент.

Скалярное состояние: отказ от модификации данных

Самый частый сценарий оптимизации — замена дорогостоящих операций над массивом одним целочисленным счетчиком, который выступает прокси-метрикой состояния.

Рассмотрим классическую задачу (LeetCode 1004: Max Consecutive Ones III): дан массив из нулей и единиц. Разрешается заменить не более $K$ нулей на единицы. Необходимо найти максимальную длину непрерывного подмассива, состоящего только из единиц.

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

Оптимальный подход требует смены перспективы: мы ничего не меняем. Мы лишь терпим присутствие нулей в окне, пока их количество не превысит лимит $K$. Валидность окна определяется единственным скалярным параметром — количеством нулей внутри него.

def longest_ones(nums, k):
    left = 0
    max_len = 0
    zeros_in_window = 0  # Скалярное состояние

    for right in range(len(nums)):
        # Фаза расширения: обновляем состояние при входе элемента
        if nums[right] == 0:
            zeros_in_window += 1

        # Фаза сужения: окно невалидно, пока нулей больше k
        while zeros_in_window > k:
            if nums[left] == 0:
                zeros_in_window -= 1  # Обновляем состояние при выходе
            left += 1

        # Окно снова валидно, обновляем глобальный результат
        max_len = max(max_len, right - left + 1)

    return max_len

В этом паттерне переменная zeros_in_window полностью инкапсулирует логику валидации. Проверка zeros_in_window > k выполняется за $O(1)$. Обратите внимание на строгую симметрию: если элемент повлиял на состояние при пересечении правой границы (right), он обязан оказать обратное влияние при пересечении левой границы (left).

Порог перехода: агрегация сложных условий

Скалярное состояние легко поддерживать, когда условие завязано на один тип элементов. Но что, если требования задачи многомерны?

Представьте условие: «Окно должно содержать как минимум 3 уникальных символа, каждый из которых встречается не менее 2 раз». Для отслеживания частот потребуется хеш-таблица (словарь). Обновление частоты конкретного символа при движении указателей занимает $O(1)$. Однако проверка самого условия становится проблемой:

# Антипаттерн проверки сложного состояния
def is_valid(freq_map):
    valid_chars = 0
    for char, count in freq_map.items():
        if count >= 2:
            valid_chars += 1
    return valid_chars >= 3

Если в алфавите задачи сотни возможных символов (обозначим их количество как $U$), вызов функции is_valid внутри цикла while сделает общую сложность алгоритма $O(N \cdot U)$. Хотя $U$ может считаться константой, при жестких ограничениях по времени это приведет к провалу.

Решение заключается во введении переменной-агрегатора (часто ее называют conditions_met или matched). Эта переменная хранит количество условий, которые в данный момент выполнены. Мы обновляем ее не путем пересчета всего словаря, а только в моменты порога перехода — когда конкретный символ достигает нужной частоты или падает ниже нее.

Механика пороговых переходов

Разберем логику обновления переменной matched для условия «символ встречается $\geq 2$ раз»:

1. При расширении окна (добавление символа c): Частота c увеличивается. Если до добавления частота была 1, а стала 2, символ только что выполнил условие. Мы делаем matched += 1. Если частота стала 3, 4 или 5, условие уже было выполнено ранее, переменная matched не меняется.

2. При сужении окна (удаление символа c): Частота c уменьшается. Если до удаления частота была 2, а стала 1, символ только что перестал выполнять условие. Мы делаем matched -= 1. Если частота упала с 5 до 4, условие все еще выполняется, matched не меняется.

Реализация этого паттерна требует хирургической точности в порядке операций:

def find_valid_window_len(s):
    freq = {}
    matched = 0
    left = 0
    min_len = float('inf')

    for right in range(len(s)):
        char_in = s[right]
        freq[char_in] = freq.get(char_in, 0) + 1

        # Порог перехода при добавлении
        if freq[char_in] == 2:
            matched += 1

        # Окно валидно, когда выполнено 3 условия
        while matched >= 3:
            min_len = min(min_len, right - left + 1)

            char_out = s[left]
            # Порог перехода при удалении проверяется ДО изменения частоты
            if freq[char_out] == 2:
                matched -= 1

            freq[char_out] -= 1
            left += 1

    return min_len if min_len != float('inf') else 0

Сложность проверки условия сжалась с $O(U)$ до $O(1)$. Цикл while matched >= 3 мгновенно оценивает статус окна, опираясь на единственное число.

Симметрия состояний и ловушки порядка выполнения

Использование вспомогательных счетчиков делает алгоритм уязвимым к логическим ошибкам, связанным с рассинхронизацией данных. Состояние окна (счетчик) и физические границы окна (индексы left и right) могут разойтись, если нарушить порядок обновления.

Существует строгий инвариант, который должен соблюдаться на каждой итерации: вспомогательная переменная должна точно отражать данные, находящиеся строго между индексами left и right включительно.

Рассмотрим типичную ошибку «смещения на единицу» (off-by-one error) при сужении окна:

# ОШИБОЧНАЯ реализация фазы сужения
while matched >= 3:
    left += 1
    char_out = s[left]
    if freq[char_out] == 2:
        matched -= 1
    freq[char_out] -= 1

В этом фрагменте указатель left сдвигается до того, как элемент по старому индексу был исключен из состояния. Переменная char_out получает символ, который теперь находится внутри нового окна, а элемент, который фактически выпал из окна, остается учтенным в freq и matched. Состояние необратимо ломается.

Правильная архитектура дельта-обновления всегда строится по принципу «прочитал — обновил состояние — сдвинул границу»:

1. Идентифицировать элемент, который собирается покинуть окно (элемент по индексу left).
2. Проверить, вызывает ли его уход пересечение порога, и обновить агрегатор (matched).
3. Обновить базовую структуру данных (уменьшить частоту в словаре).
4. Только после полного обновления логического состояния физически сдвинуть указатель (left += 1).

Тот же принцип касается фазы расширения: элемент сначала добавляется в логическое состояние, и только затем проверяется валидность нового состояния в цикле while.

Оптимизация проверки условий через скалярные состояния и пороговые агрегаторы — это мост между структурно правильным кодом и кодом, который проходит нагрузочные тесты. Отказ от повторных вычислений внутри окна требует дисциплины в управлении переменными, но взамен гарантирует истинную линейную сложность алгоритма независимо от тяжести бизнес-логики.

Обработка строковых задач: частотные словари и поиск анаграмм через скользящее окно

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

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

Частотная сигнатура: отказ от сортировки

Две строки называются анаграммами, если одну можно получить из другой перестановкой символов. Строки listen и silent — анаграммы.

Самый очевидный способ проверить две строки на анаграмму — отсортировать их в алфавитном порядке и сравнить. Если после сортировки строки идентичны, значит, они состоят из одного и того же набора символов. Временная сложность такого подхода составляет $O(K \log K)$, где $K$ — длина строки. Если нам нужно искать анаграмму длины $K$ внутри большого текста длины $N$, прикладывая отсортированный шаблон к каждой позиции, общая сложность составит $O(N \cdot K \log K)$. Для текстов длиной в сотни тысяч символов это неприемлемо медленно.

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

Мы можем преобразовать целевую строку в частотный словарь (или массив частот). Для строки aba словарь выглядит как {'a': 2, 'b': 1}. Это и есть частотная сигнатура. Любая строка, претендующая на звание анаграммы, должна обладать точно такой же сигнатурой. Построение такого словаря занимает $O(K)$ времени, а сравнение двух словарей зависит только от размера алфавита, что в контексте асимптотического анализа является константой $O(1)$.

Интеграция сигнатуры в фиксированное скользящее окно

Поиск всех анаграмм шаблона в длинной строке — классическая задача на фиксированное скользящее окно. Длина искомой анаграммы задает жесткий размер окна $K$.

Алгоритм разбивается на два логических этапа. Сначала мы строим эталонный частотный словарь для шаблона. Затем мы создаем пустой словарь для текущего окна и начинаем двигать правую границу.

Главная алгоритмическая хитрость заключается в дельта-обновлении. Когда окно сдвигается на одну позицию вправо, состав символов внутри него меняется минимально: один новый символ входит в окно, и один старый символ из него выходит. Все остальные $K - 2$ символов остаются на своих местах.

Нам не нужно пересчитывать частотный словарь окна с нуля на каждом шаге. Достаточно выполнить две операции за $O(1)$:

1. Увеличить счетчик для символа, на который указывает правая граница окна.
2. Уменьшить счетчик для символа, который остался за левой границей окна, и сдвинуть левую границу.

Если после этих двух операций частотный словарь окна полностью совпадает с эталонным словарем шаблона, мы нашли анаграмму. Индекс левой границы фиксируется как начало найденной подстроки.

Адаптация счетчика совпадений: строгое равенство против избытка

В предыдущих материалах мы рассматривали паттерн скалярного агрегатора (переменной matched), который позволяет не сравнивать словари целиком на каждом шаге, а отслеживать количество выполненных условий. При работе со строками логика пороговых переходов для переменной matched кардинально меняется в зависимости от того, ищем ли мы точную анаграмму или просто подстроку, содержащую нужные символы.

Сценарий 1: Поиск точной анаграммы

При поиске анаграмм размер окна строго фиксирован и равен длине шаблона. Это означает, что любое отклонение частоты символа от эталона делает окно невалидным.

Допустим, шаблон — строка aab. Эталонный словарь: {'a': 2, 'b': 1}. Всего уникальных символов, которые нужно сопоставить, два (буква a и буква b). Текущее окно наткнулось на подстроку aaa. Словарь окна: {'a': 3}.

В этом случае счетчик буквы a превысил эталонное значение. Для анаграммы это критическое нарушение. Переменная matched должна увеличиваться только тогда, когда частота символа в окне в точности равна частоте в шаблоне.

Правила пороговых переходов для точной анаграммы:

• При добавлении символа: если его частота в окне стала равна частоте в шаблоне, увеличиваем matched. Если частота превысила шаблонную (была равна, а стала больше), мы «сломали» идеальное совпадение — уменьшаем matched.
• При удалении символа: если до удаления частота была равна шаблонной, мы теряем совпадение — уменьшаем matched. Если частота была избыточной (больше шаблонной), а после удаления стала в точности равна ей — мы «починили» совпадение, увеличиваем matched.

Окно признается анаграммой тогда и только тогда, когда matched равен количеству уникальных символов в шаблоне.

Сценарий 2: Поиск минимального окна с заданными символами

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

Шаблон снова aab. Окно расширилось и захватило подстроку c a a x a b. Словарь окна: {'c': 1, 'a': 3, 'x': 1, 'b': 1}.

Здесь наличие лишней буквы a (три вместо двух) не является ошибкой. Условие «содержит как минимум две буквы a» выполнено. Наличие посторонних букв c и x тоже допустимо.

Правила пороговых переходов для поиска с избытком:

• При добавлении символа: если его частота в окне стала равна частоте в шаблоне, увеличиваем matched. Дальнейшее увеличение частоты этого символа игнорируется — matched не меняется, так как условие уже выполнено с запасом.
• При удалении символа: мы уменьшаем matched только в том случае, если после удаления частота символа упала ниже шаблонной. Удаление избыточных символов никак не влияет на валидность окна.

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

Обработка "мусорных" символов

В задачах на поиск подстроки по условию (как во втором сценарии) часто возникает ситуация, когда текущий символ окна вообще отсутствует в шаблоне.

Попытка добавить такой символ в словарь окна и отслеживать его частоту приведет к бессмысленному расходу памяти и процессорного времени на обновление ключей, которые никогда не повлияют на переменную matched.

Оптимальный подход требует фильтрации на этапе чтения: прежде чем обновлять частотный словарь окна и проверять пороговые переходы, алгоритм должен проверить, существует ли текущий символ в эталонном словаре шаблона. Если символа там нет, мы просто сдвигаем указатель дальше. Словарь окна должен содержать только те ключи, которые релевантны для текущей задачи. Это гарантирует, что размер словаря окна никогда не превысит размер словаря шаблона, что особенно важно при работе с расширенными кодировками вроде Unicode, где потенциальный размер алфавита огромен.

Оптимизация структур данных: Массив против Хеш-таблицы

В Python для создания частотных словарей традиционно используется встроенный тип dict или специализированный класс collections.Counter. Они универсальны, поддерживают любые хэшируемые типы данных и отлично подходят для символов Unicode.

Однако многие алгоритмические задачи искусственно ограничивают входные данные. Часто в условиях явно указано: «строка состоит только из строчных букв английского алфавита». Это ограничение — прямой сигнал к оптимизации константы времени выполнения.

Английский алфавит состоит из 26 букв. Символы в таблице ASCII расположены последовательно: от a (код 97) до z (код 122). Вместо использования хеш-таблицы с ее накладными расходами на вычисление хеша и разрешение коллизий, мы можем использовать обычный массив (список в Python) фиксированного размера 26.

Индекс в таком массиве вычисляется простой арифметической операцией: код текущего символа минус код буквы a.

# Вычисление индекса для символа char
index = ord(char) - ord('a')

Массив [0] * 26 становится идеальным частотным словарем.

• Индекс 0 хранит частоту буквы a.
• Индекс 1 — частоту буквы b.
• Индекс 25 — частоту буквы z.

Почему массив быстрее хеш-таблицы, хотя асимптотически обе структуры обеспечивают доступ за $O(1)$? Во-первых, вычисление разности кодов символов — это базовая процессорная инструкция, которая выполняется значительно быстрее алгоритма хеширования строк. Во-вторых, массив из 26 элементов занимает непрерывный и очень маленький участок памяти. Он целиком помещается в L1-кэш процессора. Хеш-таблица же разбросана по памяти, что приводит к кэш-промахам (cache misses) при интенсивном чтении и записи на каждом сдвиге скользящего окна.

Более того, при использовании массива фиксированного размера отпадает необходимость в сложной логике переменной matched. Сравнение двух массивов из 26 элементов занимает ровно 26 тактов, что является ничтожно малой константой. Во многих случаях прямое сравнение массивов window_counts == target_counts на каждом шаге цикла оказывается быстрее, чем поддержка дополнительных счетчиков пороговых переходов, из-за отсутствия ветвлений (if-else), которые могут сбивать предсказатель переходов (branch predictor) в процессоре.

Переход от строк к их частотным векторам и филигранное управление этими векторами через дельта-обновления — это вершина эволюции паттерна скользящего окна для строковых задач. Понимание разницы между строгим равенством сигнатур и допустимым избытком позволяет адаптировать этот подход как для жестких ограничений (анаграммы), так и для гибких поисковых запросов (минимальные подстроки). Выбор правильной структуры данных — массива или хеш-таблицы — завершает трансформацию алгоритма, превращая теоретическую линейную сложность $O(N)$ в максимально эффективный код на практике.

Сложные условия расширения и сжатия: работа с несколькими инвариантами одновременно

Классическое скользящее окно опирается на монотонность: добавление элемента всегда приближает нас к нарушению условия, а удаление — к его восстановлению. Но алгоритмическая реальность часто ломает эту идиллию. Если задача требует найти самую длинную подстроку, где каждый символ встречается не менее $K$ раз, расширение окна ведет себя непредсказуемо. Добавление нового уникального символа мгновенно делает окно невалидным (его частота равна 1, что меньше $K$). Должны ли мы сужать окно? Если сдвинуть левую границу, мы можем навсегда потерять шанс набрать нужные $K$ вхождений для этого символа в будущем.

Когда базовый инвариант не обладает свойством монотонности, стандартный цикл сжатия становится невозможным. В таких случаях алгоритм требует введения искусственных ограничений, расщепления логики на несколько независимых состояний или перехода от двух указателей к трем.

Искусственная монотонность: управление конфликтующими инвариантами

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

Рассмотрим упомянутую задачу: найти максимальную длину подстроки, где частота каждого присутствующего символа $\geq K$. Прямой проход не работает. Однако мы знаем физическое ограничение входных данных — английский алфавит содержит ровно 26 букв.

Вместо одного прохода мы выполняем 26 независимых проходов. В каждом проходе мы фиксируем целевое количество уникальных символов $U$ (от 1 до 26). Теперь у нас два инварианта:

1. Управляющий инвариант (монотонный): в окне должно быть ровно $U$ уникальных символов.
2. Целевой инвариант (немонотонный): каждый из этих $U$ символов должен встречаться $\geq K$ раз.

Управляющий инвариант идеален для скользящего окна. Если при расширении вправо количество уникальных символов превышает $U$, мы обязаны сжимать окно слева, пока их снова не станет $U$. Это классическая логика, которая гарантирует $O(N)$ для каждого из 26 проходов.

Внутри этого процесса мы поддерживаем состояние целевого инварианта. Нам нужны две скалярные переменные: unique_count (сколько сейчас разных букв) и k_count (сколько букв достигли порога $K$).

Логика обновления состояния на каждом шаге правого указателя выглядит так:

1. Добавляем символ в частотный словарь.
2. Если частота стала равна 1, увеличиваем unique_count.
3. Если частота стала равна $K$, увеличиваем k_count.

Затем запускается цикл сжатия, который опирается только на управляющий инвариант: пока unique_count > U, мы сдвигаем левый указатель, симметрично обновляя словарь и уменьшая счетчики при падении частот ниже $K$ или до нуля.

После того как окно стабилизировано (условие unique_count <= U выполнено), мы проверяем целевой инвариант: если unique_count == U и unique_count == k_count, значит, в окне ровно $U$ символов, и все они встречаются $\geq K$ раз. Только в этот момент мы обновляем глобальный максимум длины.

Разделение ролей — фундаментальный паттерн. Один инвариант двигает указатели, второй — пассивно наблюдает и фиксирует ответ. Итоговая сложность составляет $O(26 \cdot N)$, что асимптотически эквивалентно $O(N)$.

Комбинаторный подсчет подмассивов: математика окна

Переход от поиска экстремумов (самый длинный/короткий) к подсчету количества валидных подмассивов требует изменения математической модели окна.

Предположим, задано условие: найти количество подмассивов, сумма элементов которых строго меньше $S$ (при условии, что все числа положительные).

Когда правый указатель right добавляет элемент, а левый left сдвигается до тех пор, пока сумма не станет меньше $S$, мы получаем валидное окно [left ... right]. Ключевая ошибка начинающих — прибавлять к общему ответу единицу (считая само окно за один подмассив).

На самом деле, если окно [left ... right] валидно, то любой подмассив, заканчивающийся в индексе right и начинающийся в пределах от left до right, также валиден.

Если текущее окно содержит элементы с индексами от 2 до 5, то валидными подмассивами, заканчивающимися на индексе 5, будут:

• [5] (длина 1, начало в 5)
• [4, 5] (длина 2, начало в 4)
• [3, 4, 5] (длина 3, начало в 3)
• [2, 3, 4, 5] (длина 4, начало в 2)

Количество таких подмассивов всегда равно длине текущего окна: $right - left + 1$.

Таким образом, на каждой итерации внешнего цикла, после стабилизации левого указателя, мы прибавляем к глобальному счетчику значение $right - left + 1$. Это позволяет за один линейный проход подсчитать все возможные комбинации без вложенных циклов перебора.

Паттерн Exact(K): алгебра скользящих окон

Комбинаторный подсчет идеально работает для условий вида «не более» (At Most) или «строго меньше». Но задачи часто формулируются в виде точного равенства: «найти количество подмассивов, содержащих ровно $K$ уникальных чисел».

Попытка написать скользящее окно для условия «ровно $K$» обречена на провал из-за неоднозначности сжатия. Если в окне сейчас ровно $K$ уникальных элементов, сдвиг левого указателя может как сохранить $K$ уникальных (если мы удалили дубликат), так и уменьшить их до $K-1$ (если удалили единственный экземпляр числа). Алгоритм не понимает, в какой момент нужно остановиться, чтобы не пропустить вложенные валидные подмассивы.

Решение лежит в области теории множеств. Множество подмассивов, содержащих ровно $K$ уникальных элементов, является разностью двух множеств:

1. Подмассивы, содержащие не более $K$ уникальных элементов.
2. Подмассивы, содержащие не более $K-1$ уникальных элементов.

Отсюда рождается формула:

$$Exact(K) = AtMost(K) - AtMost(K-1)$$

Где $Exact(K)$ — искомое количество, а $AtMost(X)$ — функция, реализующая классическое скользящее окно, возвращающая сумму $right - left + 1$ на каждом шаге.

Вместо написания сложной и нестабильной логики для точного совпадения, мы пишем одну простую, железобетонную функцию at_most(k) и вызываем её дважды.

Если массив имеет вид [1, 2, 1, 2, 3], а мы ищем подмассивы с ровно 2 уникальными числами:

• at_most(2) найдет 12 подмассивов (все комбинации из единиц и двоек, плюс комбинации на стыке двоек и тройки).
• at_most(1) найдет 5 подмассивов (каждое число по отдельности, так как подряд идущих одинаковых нет).
• Ответ: $12 - 5 = 7$ подмассивов.

Этот паттерн универсален. Он применяется для задач «ровно $K$ нечетных чисел», «сумма равна ровно $S$» (для положительных чисел) и любых других метрик, где «не более» образует монотонное условие.

Техника трех указателей: оптимизация однопроходного поиска

Вызов функции at_most дважды требует двух проходов по массиву. В большинстве случаев это приемлемо, так как $O(2N)$ — это всё ещё $O(N)$. Но если данные поступают в виде непрерывного потока (stream), который нельзя прочитать дважды, или требуется экстремальная оптимизация константы времени, используется техника трех указателей.

Мы физически объединяем два окна в один проход. Для этого нам понадобятся один правый указатель right и два левых: left_far (дальняя граница) и left_near (ближняя граница).

Концепция строится на одновременном поддержании двух инвариантов в рамках одного цикла:

• Окно [left_far ... right] поддерживает условие «не более $K$ уникальных».
• Окно [left_near ... right] поддерживает условие «не более $K-1$ уникальных».

На каждом шаге right мы сначала обновляем состояние для дальнего окна и сдвигаем left_far, пока уникальных элементов больше $K$. Затем мы делаем то же самое для ближнего окна — сдвигаем left_near, пока уникальных элементов больше $K-1$.

Разница между индексами левых указателей в любой момент времени дает точное количество валидных стартовых позиций для текущего right. Формула подсчета на каждом шаге трансформируется: вместо $right - left + 1$ мы прибавляем к ответу $left\_near - left\_far$.

Разберем механику на массиве [1, 2, 1, 3], ищем ровно $K=2$ уникальных числа:

1. right = 0 (число 1). left_far = 0, left_near = 1 (так как для $K-1=1$ уникальных окно должно быть пустым, ближний указатель обгоняет правый). Разница $1 - 0 = 1$. Но постойте, у нас пока только 1 уникальное число, а нужно 2. Логика ломается? Нет. В реализации с тремя указателями мы прибавляем разницу только если дальнее окно содержит ровно $K$ уникальных элементов.
2. right = 1 (число 2). В дальнем окне [1, 2] ровно 2 уникальных. left_far = 0. Ближнее окно должно содержать $\leq 1$ уникальных, поэтому left_near сдвигается до индекса 1 (окно [2]). Разница $1 - 0 = 1$. Подмассив: [1, 2].
3. right = 2 (число 1). Дальнее окно [1, 2, 1] — 2 уникальных, left_far = 0. Ближнее окно [2, 1] содержит 2 уникальных, сдвигаем left_near до индекса 2 (окно [1]). Разница $2 - 0 = 2$. Подмассивы: [1, 2, 1] и [2, 1].
4. right = 3 (число 3). Дальнее окно берет тройку, уникальных становится 3. Сдвигаем left_far до индекса 2 (окно [1, 3]). Ближнее окно берет тройку, уникальных 2. Сдвигаем left_near до индекса 3 (окно [3]). Разница $3 - 2 = 1$. Подмассив: [1, 3].

Суммарно найдено 4 подмассива. Третий указатель выступает в роли локального разделителя, отсекающего зону, где условие выполняется ровно, от зоны, где оно проседает до $K-1$.

Каскадные условия сжатия и отложенная валидация

В сложных задачах левый указатель может двигаться не по одному простому правилу, а по каскаду условий. Это происходит, когда мы ищем минимальное окно, но внутри него допускаются «мусорные» элементы, которые нужно агрессивно отсекать при сжатии.

Рассмотрим ситуацию, где окно валидно, если содержит определенный набор символов, но мы хотим найти минимальную длину. Правый указатель расширяет окно, пока мы не соберем все нужные символы. Как только окно стало валидным, начинается фаза сжатия.

Вместо проверки одного счетчика, левый указатель должен проверять текущий элемент на принадлежность к двум категориям:

1. Является ли элемент на позиции left избыточным (его частота в окне больше, чем требуется)?
2. Является ли элемент вообще нерелевантным (отсутствует в искомом шаблоне)?

Цикл while для левого указателя будет работать до тех пор, пока выполняется хотя бы одно из этих условий. Если мы видим мусорный символ — смело сдвигаем left и удаляем его из частотного словаря окна. Если мы видим полезный символ, но его счетчик показывает переизбыток — также сдвигаем left, уменьшая счетчик.

Остановка левого указателя происходит только тогда, когда на позиции left находится критически важный символ, удаление которого немедленно сделает окно невалидным (его текущая частота равна минимально необходимой). Только в этой точке остановки мы фиксируем длину окна как потенциальный минимум.

После фиксации минимума мы принудительно сдвигаем left еще на один шаг вправо, намеренно ломая валидность окна. Это действие возвращает алгоритм в фазу расширения — правый указатель снова начинает движение в поисках следующего вхождения потерянного символа.

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

Edge cases и отладка: обработка пустых вводов, границ массива и единичных элементов

Идеально спроектированный алгоритм со сложностью $O(N)$, который блестяще работает на тестовых примерах из описания задачи, регулярно разбивается о суровую реальность проверяющей системы. Ошибка IndexError: list index out of range на скрытом тесте №4 или неверный ответ на массиве из одного элемента — классический сценарий провала на алгоритмической секции. Паттерны двух указателей и скользящего окна особенно уязвимы к граничным случаям, так как они напрямую манипулируют индексами памяти и полагаются на неявные инварианты структуры данных.

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

Анатомия IndexError: агрессивные внутренние циклы

Самая частая причина падения программ с двумя указателями — выход за границы массива (Out of Bounds). В базовом цикле for right in range(len(nums)) или while right < len(nums) правый указатель надежно зафиксирован. Проблема возникает, когда внутри основного цикла появляются вложенные циклы while, задача которых — быстро пропустить группу элементов или агрессивно сузить окно.

Опасность короткого замыкания

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

# Опасный код
while nums[right] == nums[right - 1]:
    right += 1

Если массив состоит из одинаковых элементов (например, [2, 2, 2]), указатель right дойдет до последнего элемента, условие nums[2] == nums[1] выполнится, right станет равен 3. На следующей итерации интерпретатор попытается вычислить nums[3] == nums[2]. Произойдет обращение к несуществующему индексу 3, и программа завершится с ошибкой.

Исправление требует явного контроля границ, но здесь кроется вторая ловушка — порядок операндов в условии. Язык Python использует ленивое вычисление (short-circuit evaluation) логических операторов.

# Ошибка: граница проверяется слишком поздно
while nums[right] == nums[right - 1] and right < len(nums):
    right += 1

# Безопасный код: граница защищает обращение к памяти
while right < len(nums) and nums[right] == nums[right - 1]:
    right += 1

В безопасном варианте, когда right достигает длины массива, условие right < len(nums) возвращает False. Благодаря ленивому вычислению, правая часть с обращением к nums[right] даже не будет выполняться, спасая программу от падения.

Перехлест указателей при сужении окна

В динамическом скользящем окне внутренний цикл отвечает за сужение (сдвиг left). Обычно условием выступает невалидность окна (например, сумма превысила лимит).

# Поиск минимального окна с суммой >= target
while current_sum >= target:
    min_length = min(min_length, right - left + 1)
    current_sum -= nums[left]
    left += 1

Этот код выглядит корректным и работает для массивов с положительными числами. Но что, если в результате агрессивного сжатия левый указатель обгонит правый? В классических задачах на сумму положительных чисел current_sum станет равна нулю (или меньше target), и цикл остановится. Однако при работе со строками или сложными инвариантами (например, удаление символов до тех пор, пока не встретится определенный маркер) left может беспрепятственно расти.

Правило: любой внутренний цикл, двигающий left, должен быть защищен условием left <= right (или left < len(nums), в зависимости от логики), если инвариант задачи не гарантирует естественной остановки.

# Защищенное сужение окна
while left <= right and not is_valid(window_state):
    remove_from_state(nums[left])
    left += 1

Ловушка пустого ввода и единичного элемента

Проверяющие системы всегда тестируют алгоритмы на вырожденных данных. Массив нулевой длины [] и массив из одного элемента [42] — два главных стресс-теста для логики инициализации.

Пустой массив (N = 0)

Для паттерна встречных указателей пустой массив смертелен, если инициализация выглядит как right = len(nums) - 1. В этом случае right станет равен -1.

Если цикл задан как while left < right:, то при left = 0 и right = -1 условие ложно, цикл не выполнится, и программа завершится корректно (если возвращаемое значение по умолчанию настроено верно). Но если внутри кода есть прямое обращение к nums[right] до проверки условия, произойдет чтение с конца массива (в Python индекс -1 валиден и указывает на последний элемент, но в пустом массиве нет и его, что вызовет IndexError).

Для скользящего окна цикл for right in range(len(nums)) элегантно обрабатывает пустой массив: range(0) просто не сгенерирует ни одной итерации. Однако, если алгоритм ожидает вернуть максимум, а начальное значение переменной max_len задано как float('-inf'), пустой ввод вернет минус бесконечность вместо логичного нуля.

Решение: Ранний возврат (Fast fail). В 99% задач на два указателя пустой ввод не содержит ответа.

if not nums:
    return 0 # или [], или "", в зависимости от сигнатуры

Единичный элемент (N = 1)

Массив из одного элемента ломает алгоритмы, которые жестко ожидают пару. Рассмотрим задачу проверки палиндрома. Строка "a" — это палиндром.

При встречных указателях: left = 0, right = 0. Если мы используем строгое неравенство while left < right:, цикл не выполнится ни разу. Если в конце функции стоит return True, алгоритм выдаст правильный ответ, даже не проверив символ. Это корректное поведение, так как один символ симметричен сам себе.

Но если задача требует обработать каждый элемент (например, возвести в квадрат отсортированный массив и слить результаты), строгое неравенство left < right оставит центральный элемент (или единственный элемент) необработанным. В таких случаях необходимо использовать нестрогое неравенство while left <= right:.

Выбор между < и <= зависит исключительно от того, может ли один элемент формировать валидный ответ или требовать обработки независимо от наличия пары.

Бесконечные циклы и застрявшие указатели

Если программа превышает лимит времени (Time Limit Exceeded, TLE) на небольшом тесте, причина редко кроется в асимптотике $O(N^2)$ вместо $O(N)$. Скорее всего, один из указателей застрял, породив бесконечный цикл.

Это происходит, когда логика ветвления (if-elif-else) внутри цикла while не гарантирует изменения состояния указателей на каждой итерации.

Рассмотрим поиск пары чисел с суммой target (Two Sum II) с обработкой дубликатов:

# Ошибка: зацикливание при равенстве
while left < right:
    current_sum = nums[left] + nums[right]
    if current_sum < target:
        left += 1
    elif current_sum > target:
        right -= 1
    else:
        results.append((nums[left], nums[right]))
        # Забыли сдвинуть указатели!

В блоке else найдена пара. Результат сохранен, но ни left, ни right не изменились. На следующей итерации current_sum будет точно такой же, и программа навсегда застрянет в этом блоке. При нахождении ответа необходимо обязательно сдвинуть хотя бы один (а чаще оба) указателя.

Другой сценарий застревания — неправильная работа с пропусками. Если мы хотим пропустить символ, не являющийся буквой (при проверке палиндрома):

while left < right:
    if not s[left].isalnum():
        left += 1
    if not s[right].isalnum():
        right -= 1

    if s[left].lower() != s[right].lower(): # Ошибка: сравнение мусора
        return False
    # ...

Здесь left сдвинулся, но мы сразу же, на этой же итерации, обращаемся к s[left]. А что если новый символ тоже не буква? Сравнение произойдет некорректно. Правильный паттерн требует внутренних циклов для поиска следующего валидного элемента:

while left < right:
    while left < right and not s[left].isalnum():
        left += 1
    while left < right and not s[right].isalnum():
        right -= 1

    if s[left].lower() != s[right].lower():
        return False
    left += 1
    right -= 1

Ошибка на единицу: математика индексов

Ошибка на единицу (Off-by-one error) — классическая проблема при вычислении длин и расстояний. В паттернах с указателями она возникает из-за путаницы между инклюзивными и эксклюзивными границами.

В Python срезы работают по принципу [start:end), где правая граница не включается. Длина такого среза равна end - start. Однако в скользящем окне указатель right обычно указывает на текущий обрабатываемый элемент, то есть окно является инклюзивным с обеих сторон: [left, right].

Количество элементов в инклюзивном окне всегда равно right - left + 1. Если left = 2, а right = 5, элементы в окне имеют индексы 2, 3, 4, 5. Их ровно 4. Формула 5 - 2 даст 3, что приведет к неверному ответу.

Исключение из этого правила — задачи на физическое расстояние между указателями, а не на количество элементов между ними. Например, в задаче о максимальной площади контейнера (Container With Most Water) шириной выступает расстояние между стенками. Если стенки стоят на индексах 2 и 5, ширина равна 5 - 2 = 3. Здесь +1 не требуется, так как мы считаем интервалы, а не сами элементы.

Рассинхронизация состояния и указателей

Скользящее окно переменного размера — это механизм из трех шестеренок: правый указатель (расширение), левый указатель (сужение) и переменная состояния (сумма, счетчик, словарь). Если порядок их обновления нарушен, возникает эффект «призрачного состояния» — окно находится в одних границах, а переменная состояния отражает данные для других границ.

Рассмотрим типичную ошибку при сужении окна:

# Ошибка: рассинхронизация при сужении
while current_sum > target:
    left += 1
    current_sum -= nums[left] # Вычитаем новый left, а не старый!

В этом коде мы сначала сдвинули left, а затем попытались удалить из суммы элемент, на который left теперь указывает. Элемент, который реально покинул окно (старый left), остался в current_sum навсегда. Состояние безвозвратно испорчено.

Золотой стандарт порядка операций (Инвариант синхронизации) требует строгой последовательности действий:

Фаза расширения:

1. Прочитать элемент nums[right].
2. Добавить его влияние в состояние окна.

Фаза сужения (внутренний цикл):

1. Проверить, нарушено ли условие (пока невалидно).
2. Удалить влияние элемента nums[left] из состояния окна.
3. Сдвинуть left на 1 вправо.

Фаза фиксации результата:

1. Только после того как окно снова стало валидным (внутренний цикл завершен), обновить глобальный ответ (максимум/минимум), используя текущие left и right.

# Идеальный каркас динамического окна
for right in range(len(nums)):
    # 1. Расширение
    state.add(nums[right])

    # 2. Сужение (восстановление инварианта)
    while not is_valid(state):
        state.remove(nums[left]) # Сначала чистим состояние
        left += 1                # Только потом двигаем границу

    # 3. Фиксация результата (окно 100% валидно)
    max_len = max(max_len, right - left + 1)

Отклонение от этого порядка допустимо только в специфических задачах (например, поиск кратчайшего окна, где фиксация результата происходит внутри цикла сужения), но логика «сначала удали из состояния, потом сдвинь указатель» остается незыблемой.

Граничные случаи при инициализации словарей

При работе со строками состояние часто хранится в частотном словаре (хеш-таблице). Ошибка инициализации здесь связана с обращением к несуществующим ключам.

При сужении окна мы удаляем символ: window_counts[s[left]] -= 1. Если словарь реализован через стандартный dict в Python, и символ по какой-то причине не был добавлен ранее (логическая ошибка в фазе расширения), программа упадет с KeyError.

Использование collections.defaultdict(int) маскирует эту проблему: обращение к несуществующему ключу просто создаст его со значением 0, а затем вычтет 1, сделав значение -1. Программа не упадет, но логика пороговых переходов (счетчик matched) будет сломана, так как появятся отрицательные частоты.

Лучшая практика отладки строковых окон — использовать стандартный dict на этапе написания кода. Если возникает KeyError, это четкий сигнал о рассинхронизации: вы пытаетесь удалить из окна то, чего там нет. Переход на defaultdict или collections.Counter стоит делать только тогда, когда вы полностью уверены в синхронности движения left и right.

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

Алгоритмические паттерны редко работают в вакууме. В чистом виде метод двух указателей или скользящее окно требует идеального ландшафта: отсортированного массива, монотонного условия или непрерывной последовательности. Когда данные хаотичны, содержат скрытые зависимости или требуют учета глобального контекста, одного прохода указателями становится недостаточно. Возникает необходимость в предварительной обработке данных — трансформации, которая создаст нужный ландшафт для эффективного применения $O(N)$ алгоритмов.

Смена парадигмы: от суммы к разности

Классическая задача поиска пары чисел с заданной суммой (Two Sum) в отсортированном массиве решается встречными указателями. Логика опирается на строгую монотонность: если сумма слишком велика, мы сдвигаем правый указатель влево, гарантированно уменьшая результат. Если мала — сдвигаем левый указатель вправо, увеличивая сумму.

Ситуация кардинально меняется, если требуется найти пару чисел с заданной абсолютной разностью: $|A - B| = K$.

При использовании встречных указателей монотонность разрушается. Если текущая разность больше $K$, сдвиг правого указателя влево уменьшит разность. Но сдвиг левого указателя вправо тоже уменьшит разность. Алгоритм теряет детерминированность: невозможно однозначно выбрать, какой указатель двигать, не рискуя пропустить правильный ответ.

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

Пусть массив отсортирован по возрастанию: [1, 2, 5, 7, 9], и мы ищем разность $K = 4$. Устанавливаем оба указателя в начало: left = 0, right = 1. Разность вычисляется как $nums[right] - nums[left]$.

Правила сдвига строго детерминированы:

1. Если разность равна $K$ — пара найдена.
2. Если разность меньше $K$ — нужно ее увеличить. Так как массив отсортирован, увеличение достигается сдвигом right вправо (мы берем большее уменьшаемое).
3. Если разность больше $K$ — нужно ее уменьшить. Это достигается сдвигом left вправо (мы берем большее вычитаемое).

Особый граничный случай возникает, когда указатели указывают на один и тот же элемент (left == right), что дает разность $0$. Если искомая разность $K > 0$, алгоритм должен принудительно сдвинуть right на шаг вперед, чтобы избежать сравнения элемента с самим собой.

Этот подход демонстрирует, как предварительная обработка (сортировка за $O(N \log N)$) меняет саму топологию задачи, позволяя применить паттерн параллельных указателей за $O(N)$ и получить итоговую сложность $O(N \log N)$ вместо наивного перебора за $O(N^2)$.

Виртуальная предварительная обработка: симуляция вместо памяти

Часто предварительная обработка подразумевает создание новой структуры данных. Однако выделение $O(N)$ памяти под новые массивы или строки может быть недопустимо по условиям задачи. В таких случаях применяется виртуальная предварительная обработка — состояние вычисляется динамически прямо во время движения указателей.

Яркий пример — сравнение двух строк, содержащих символы удаления (Backspace String Compare). Символ # означает удаление предыдущего введенного символа. Строки "ab#c" и "ad#c" в итоге равны "ac".

Наивный подход требует прохода по строкам со стеком для формирования итоговых версий, что занимает $O(N)$ памяти. Чтобы решить задачу за $O(1)$ памяти, необходимо читать строки с конца, симулируя процесс применения backspace «на лету».

Два указателя устанавливаются на последние символы обеих строк. Для каждой строки заводится независимый счетчик skip, который накапливает количество символов #.

Механика обратного чтения:

• Если текущий символ — #, мы увеличиваем skip и сдвигаем указатель влево.
• Если текущий символ — обычная буква, но skip > 0, мы игнорируем эту букву (она была бы удалена), уменьшаем skip и сдвигаем указатель влево.
• Если текущий символ — обычная буква и skip == 0, это означает, что буква гарантированно попадет в итоговую строку. В этот момент указатель останавливается.

Когда оба указателя останавливаются на «выживших» символах, происходит их сравнение. Если они не совпадают — строки разные. Если один указатель исчерпал строку, а другой остановился на валидном символе — строки разные.

Здесь два указателя не просто перебирают элементы, они работают поверх виртуального слоя данных, который распаковывается в реальном времени. Это избавляет от необходимости физически конструировать предварительно обработанные строки.

Предвычисление ландшафта: префиксные максимумы

Существуют задачи, где локального контекста (значений под указателями) критически мало для принятия решения. Указателям требуется знать глобальную информацию о данных, которые находятся далеко впереди или позади. Самый известный пример такого класса — задача о сборе дождевой воды (Trapping Rain Water).

Дан массив высот рельефа, например [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. Нужно вычислить, сколько единиц воды задержится в углублениях после дождя.

Для любого индекса $i$ объем воды над ним определяется исключительно двумя глобальными параметрами: самой высокой точкой слева от $i$ и самой высокой точкой справа от $i$. Вода поднимется ровно до уровня меньшей из этих двух вершин, минус высота самого рельефа в точке $i$.

Формула локального объема: $Water[i] = \max(0, \min(MaxLeft, MaxRight) - height[i])$.

Проблема в том, что при линейном проходе мы не знаем $MaxRight$. Наивный поиск максимумов для каждого индекса дает $O(N^2)$.

Первый шаг к оптимизации — явная предварительная обработка. Мы создаем два дополнительных массива:

1. left_max — заполняется слева направо. Каждый элемент хранит максимум от начала до текущего индекса.
2. right_max — заполняется справа налево. Каждый элемент хранит максимум от конца до текущего индекса.

После этого мы проходим по массиву третий раз, применяя формулу за $O(1)$ для каждого столбца. Временная сложность падает до $O(N)$, но ценой выделения $O(N)$ дополнительной памяти для двух массивов.

Синтез: поглощение предвычислений встречными указателями

Высший пилотаж алгоритмической оптимизации — взять логику, требующую $O(N)$ памяти для предвычислений, и встроить ее в логику движения двух указателей, сократив память до $O(1)$. В задаче о дождевой воде это достигается через понимание инварианта узкого горлышка.

Вернемся к формуле: уровень воды зависит от $\min(MaxLeft, MaxRight)$. Нам не обязательно знать точные значения обоих максимумов. Нам достаточно знать, какой из них меньше.

Мы устанавливаем встречные указатели: left = 0 и right = N - 1. Вместо массивов мы используем две скалярные переменные: current_left_max и current_right_max, которые обновляются по мере движения указателей к центру.

Ключевая логика принятия решений: Сравниваем height[left] и height[right]. Если height[left] < height[right], мы делаем фундаментальный вывод: current_left_max гарантированно меньше (или равен) истинному глобальному максимуму справа. Даже если где-то между left и right скрывается гигантская гора, она лишь увеличит правый максимум, но узким горлышком для индекса left все равно останется current_left_max. Следовательно, мы можем безопасно вычислить объем воды для left, обновить current_left_max и сдвинуть left вправо.

Если height[left] \geq height[right], логика зеркальна. Узким горлышком для индекса right является current_right_max. Мы вычисляем воду для right, обновляем current_right_max и сдвигаем right влево.

В этом синтезе два указателя выполняют двойную работу: они динамически строят префиксный и суффиксный максимумы (заменяя массивы) и одновременно вычисляют итоговый ответ. Предварительная обработка полностью растворилась в механике обхода.

Развертка циклических структур

Еще один частый сценарий, требующий трансформации данных перед запуском указателей — циклические массивы. В таких структурах за последним элементом логически следует первый.

Классическая задача: найти максимальную сумму подмассива длины $K$ в циклическом буфере. Например, в массиве [5, -1, -2, 8] при $K = 2$ максимальную сумму дает подмассив, состоящий из последнего и первого элементов: [8, 5] (сумма 13).

Стандартное скользящее окно остановится, когда правый указатель достигнет конца массива. Чтобы окно могло «перешагнуть» через границу, применяется концептуальная предварительная обработка — конкатенация массива с самим собой: arr = arr + arr. Массив [5, -1, -2, 8] превращается в [5, -1, -2, 8, 5, -1, -2, 8]. На таком удвоенном массиве обычное скользящее окно отработает корректно и найдет ответ.

Однако физическое удвоение массива требует $O(N)$ памяти и времени на копирование. Как и в предыдущих случаях, мы можем заменить физическую трансформацию математической симуляцией.

Размер массива остается равным $N$. Правый указатель скользящего окна движется не от $0$ до $N-1$, а от $0$ до $2N - 1$ (или до $N + K - 1$, чтобы окно успело перевалить через край). При обращении к элементам массива используется операция взятия остатка от деления: arr[right % N].

Если $N = 4$, то при $right = 4$ мы обратимся к $arr[4 \pmod 4] = arr[0]$. Окно бесшовно перейдет на начало массива. Вся логика добавления элемента в окно и удаления выходящего элемента ($right - K$) остается неизменной, достаточно лишь обернуть все индексы в оператор % N.

Комбинирование двух указателей с предварительной обработкой — физической или виртуальной — это переход от прямолинейного применения шаблона к инженерному проектированию алгоритма. Сортировка упорядочивает хаос, виртуализация экономит память, а понимание инвариантов позволяет встроить тяжелые предвычисления в легковесный проход. Именно на стыке этих техник рождаются оптимальные решения, требующие минимальных ресурсов при максимальной скорости.