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

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

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

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

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

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

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

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

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

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

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

!Матрица пространства поиска и отсечение вариантов

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

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

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

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

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

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

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

!Анимация встречных указателей для поиска суммы

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

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

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

Проверка на палиндром: left и right сравнивают символы с краев строки, двигаясь к центру. Если символы не совпадают — это не палиндром.

Реверс массива in-place: left и right меняют местами элементы, на которые указывают, и делают шаг навстречу друг другу.

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

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

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

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

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

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

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

!Анимация параллельных указателей при перемещении нулей

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

Указатель reader (в коде это переменная цикла) безусловно проходит каждый элемент массива.

Указатель writer фиксирует границу обработанной части. Всё, что находится строго до индекса writer, гарантированно не является нулем.

Пространство между writer и reader — это зона, где скапливаются найденные нули.

Когда reader встречает ненулевое число, оно «перепрыгивает» через зону нулей на позицию writer, а первый ноль из этой зоны отправляется на место reader.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Левый указатель left стартует с индекса , правый right — с индекса .

Если символ под left не является буквой или цифрой, мы просто сдвигаем left вправо.

Аналогично, если символ под right — мусорный, сдвигаем right влево.

Когда оба указателя стоят на значащих символах, мы сравниваем их (приведя к одному регистру). Если они не равны — перед нами не палиндром.

Если равны, сдвигаем оба указателя навстречу друг другу.

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

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

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

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

Площадь контейнера зависит от двух факторов: расстояния между линиями (ширины) и высоты самой короткой из двух линий (вода перельется через край более низкой стенки). Формула площади: .

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

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

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

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

!Интерактивная визуализация поиска максимальной площади контейнера

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

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

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

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

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

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

Фиксация первого элемента. Мы запускаем цикл for i in range(len(nums) - 2). Элемент nums[i] становится нашим .

Поиск пары. Теперь нам нужно найти такие и в оставшейся части массива (от i + 1 до конца), чтобы . Это классическая задача Two Sum II, решаемая встречными указателями left и right.

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

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

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

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

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

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

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

!Пошаговая визуализация алгоритма 3Sum с пропуском дубликатов

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

Заметьте, что внутри циклов пропуска дубликатов 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].

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

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

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

!Схема заполнения результирующего массива квадратов

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

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

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

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

Какое условие остановки? Если вы ищете пару или проверяете симметрию — используйте left < right. Если вы обрабатываете каждый элемент и строите новую структуру — используйте left <= right.

Защищены ли вложенные циклы? Любой внутренний цикл while, который сдвигает указатель (например, для пропуска дубликатов или мусорных символов), должен дублировать проверку left < right. Иначе гарантирован выход за границы массива.

Движутся ли указатели при любом исходе? Частая ошибка новичков — забыть сдвинуть указатели в блоке if/else, что приводит к бесконечному циклу. На каждой итерации основного цикла while` хотя бы один из указателей должен изменить свое значение.

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

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

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

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

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

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

!Сдвиг элементов массива при удалении

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

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

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

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

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

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

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

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

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

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

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

Если массив пуст, возвращаем 0.

Первый элемент массива nums[0] всегда уникален в рамках просмотренной части, поэтому Писатель (slow) начинает работу с индекса 1 (это место для записи второго уникального элемента).

Читатель (fast) также начинает с индекса 1 и идет до конца массива.

На каждом шаге Читатель сравнивает текущий элемент nums[fast] с последним уникальным элементом, который мы сохранили. Последний сохраненный элемент всегда находится на позиции slow - 1.

Если nums[fast] == nums[slow - 1], это дубликат. Читатель просто идет дальше.

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

!Визуализация работы Читателя и Писателя при удалении дубликатов

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

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

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

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

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

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

Алгоритм:

Первые два элемента массива всегда допустимы (даже если они одинаковые, это максимум пара). Поэтому Писатель и Читатель начинают с индекса 2.

Читатель проверяет: если nums[fast] != nums[slow - 2], значит, добавление nums[fast] безопасно, оно не создаст третью копию.

Копируем элемент и сдвигаем Писателя.

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

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

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

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

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

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

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

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

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

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

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

p1 указывает на последний значащий элемент в nums1 (индекс ).

p2 указывает на последний элемент в nums2 (индекс ).

p (наш Писатель) указывает на самую последнюю ячейку в nums1 (индекс ).

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

!Пошаговое слияние отсортированных массивов с конца

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

Разбор граничных случаев (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 дней вы будете заново складывать показатели за следующие семь суток, вы совершите множество лишних действий. Завтрашняя неделя отличается от сегодняшней ровно на два дня: один день ушел в прошлое, один добавился в будущем. Остальные пять дней между ними абсолютно идентичны. Зачем складывать их заново? Этот простой жизненный принцип лежит в основе одного из самых мощных алгоритмических паттернов — скользящего окна.

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

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

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

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

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

!Сравнение наивного перебора и скользящего окна

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

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

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

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

Инициализация (Bootstrapping): первоначальное заполнение окна. Мы вычисляем состояние для первых элементов массива.

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

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

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

!Пошаговое движение скользящего окна

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

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

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

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

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

Проверим на примере: .

Инициализация забрала индексы .

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

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

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

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

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

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

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

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

Для суммы: операция сложения обратима вычитанием (sum -= arr[i - k]).

Для счетчика: инкремент обратим декрементом (count -= 1).

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

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

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

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

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

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

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

Защита от граничных случаев (Guard Clauses): Проверка длины массива. Если , окно сформировать невозможно.

Начальное состояние: Аккумулятор для текущего окна и переменная для хранения глобального ответа (максимума, минимума).

Первичный цикл for i in range(k): Наполнение аккумулятора первыми элементами.

Фиксация первого ответа: Копирование значения аккумулятора в глобальный ответ.

Вторичный цикл for i in range(k, n):

- Изменение аккумулятора с учетом arr[i]. - Изменение аккумулятора с учетом arr[i - k]. - Обновление глобального ответа.

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

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