Алгоритмы на массивах · модуль 8 · два указателя
Глава 8.1
Два указателя
на собеседованиях и в работе
В этой главе разобрано, откуда известно, что техника двух указателей нужна. Сначала — как устроена алгоритмическая секция собеседования и в каких открытых программах подготовки эта техника стоит отдельной темой. Затем — где тот же приём работает в обычных программах. В конце — три формы техники и карта модуля.
- Категория
- Обзор темы
- Уровень
- Начальный
- Опирается на
- Занятие 7: индексы, границы, указатели чтения и записи
- Зачем это знать
- Понимать, какие задачи модуля встретятся на интервью
§1Как устроена алгоритмическая секция
Во многих IT-компаниях собеседование разработчика включает алгоритмическую секцию. Кандидату дают задачу, он придумывает алгоритм, пишет код в онлайн-редакторе и объясняет, почему решение верное и сколько оно стоит по времени и памяти. Разберём, как её описывает сама компания, на примере Яндекса — у него это описание открыто.
«В течение часа вас попросят решить две задачи… Мы понимаем, что писать код в любимой IDE было бы значительно проще, поэтому не требуем досконального знания всех сигнатур методов. Но ждём, что вы готовы обосновать, почему выбрали именно такие методы и знаете с какой сложностью они работают».
Про первую из двух задач в журнале Яндекс Образования сказано: «Первый этап секции обычно достаточно простой. Задача решается одним или несколькими проходами по массиву и, возможно, предварительной сортировкой с помощью стандартного вызова». Техника двух указателей — один из способов решать такие задачи: один проход по массиву, иногда после сортировки.
| Что сказано в описании секции | Где это в модуле |
|---|---|
| Час на две задачи, первую желательно решить за полчаса | Задача 1 модуля — типичная первая задача секции: один проход по отсортированному массиву |
| Начинать с тестовых примеров, до кода | Глава 8.3: вопросы и примеры до решения |
| Обосновать выбор метода и его сложность | Главы 8.4, 8.5: почему указатели не пропускают ответ и почему это O(n) |
| Однократный проход: убедиться, что массив пройден целиком и один раз | Главы 8.7, 8.8: указатели чтения и записи |
| Проверить код на своих примерах, найти ошибку самому | Глава 8.9: типичные ошибки и тесты, которые их ловят |
§2Где техника стоит отдельной темой
Кроме описания секции, на то, что тему спрашивают, указывают программы подготовки к собеседованиям: в них два указателя выделены отдельным разделом. Каждый источник в таблице можно открыть и проверить.
| Источник | Что там про два указателя |
|---|---|
| Тренировки по алгоритмам от Яндекса, лекция 5 | Лекция «Префиксные суммы и два указателя» и домашнее задание к ней |
| LeetCode · Top Interview 150 | Раздел Two Pointers из пяти задач; первые четыре задачи раздела Array / String тоже решаются указателями |
| NeetCode · Two Pointers | Отдельный раздел со своим списком задач |
| algoprog.ru · П. Калинин | «Краткая теория про два указателя»: второй указатель движется только в одну сторону, его не нужно возвращать |
§3Задачи с собеседований
На LeetCode у каждой задачи есть метки техник. У всех задач ниже стоит метка Two Pointers, это проверено по данным сайта. В таблице — номер и название задачи, сложность по оценке LeetCode, суть задачи и место, где она разобрана в курсе.
| Номер и название | Сложность | Что нужно сделать | Где в курсе |
|---|---|---|---|
| 167 · Two Sum II | Medium | В отсортированном массиве найти два числа с заданной суммой | Главы 8.4–8.6, задача 1 |
| 26 · Remove Duplicates from Sorted Array | Easy | Убрать повторы из отсортированного массива на месте | Глава 8.7, задача 2 |
| 443 · String Compression | Medium | Заменить серии одинаковых символов на символ и число на месте | Глава 8.7, задача 3 |
| 283 · Move Zeroes | Easy | Перенести нули в конец, сохранив порядок остальных | Глава 8.8 |
| 75 · Sort Colors | Medium | Разложить 0, 1 и 2 по группам за один проход | Глава 8.8, разобрана с прогоном |
| 977 · Squares of a Sorted Array | Easy | Квадраты отсортированного массива с отрицательными числами, по возрастанию | Домашнее задание |
| 392 · Is Subsequence | Easy | Проверить, получается ли слово из текста вычёркиванием букв | Глава 8.7 |
| 88 · Merge Sorted Array | Easy | Слить два отсортированных массива в один | Занятие 31, слияние |
| 80 · Remove Duplicates from Sorted Array II | Medium | То же, что 26, но разрешено не больше двух одинаковых | Домашнее задание, задача 2: функция с ошибкой |
| 125 · Valid Palindrome | Easy | Проверить, читается ли строка одинаково с обеих сторон | Занятие 14; дополнительные задачи, extra.py |
| 11 · Container With Most Water | Medium | Выбрать две стенки, между которыми помещается больше всего воды | Дополнительные задачи, extra.py |
| 15 · 3Sum | Medium | Найти все тройки с нулевой суммой: сортировка и указатели внутри цикла | Дополнительные задачи, extra.py |
В журнале Яндекс Образования приведена задача: «дан массив чисел, требуется найти число подмассивов, в которых значения всех чисел различны». Её тоже решают двумя указателями в одну сторону вместе со словарём. Такие указатели называют скользящим окном — это тема занятий 9 и 10.
§4Где приём работает в программах
Тот же приём работает внутри инструментов, которыми пользуются каждый день. В каждом случае данные уже упорядочены или читаются по порядку, и два индекса обходят их за один проход.
- Сортировка в Python.
sorted()иlist.sort()(алгоритм Timsort) сливают уже отсортированные участки списка, и по каждому участку идёт свой указатель. - Удаление повторов. Команда
uniqв Linux сравнивает каждую строку с последней оставленной — это задача 2 модуля. - Сжатие изображений. Формат BMP умеет записывать подряд идущие одинаковые пиксели парой «число повторов, значение» — это задача 3.
- Быстрая сортировка. Её основной шаг, разделение, в варианте Хоара делается двумя указателями навстречу — глава 8.8.
- Подбор под сумму. Два товара на сумму сертификата или два платежа на сумму из выписки ищутся в отсортированном списке за один проход — задача 1.
§5Указатель и два указателя
В занятии 7 указатели уже встречались: i и j при развороте участка, r и w при удалении спама. Ниже сначала пример из жизни, на котором видно, как работают два указателя, затем точные определения.
Книги на полке стоят по толщине. Нужно найти две книги, которые вместе займут ровно 10 см. Один человек встаёт у тонкого края, второй — у толстого. Если пара толще нужного, второй берёт книгу тоньше; если тоньше — первый берёт книгу толще.
Полка — отсортированный список, люди — индексы i и j, «взять книгу тоньше» — j -= 1. Каждый шаг убирает одну книгу из рассмотрения, поэтому шагов не больше, чем книг.
Где сравнение неточноЛюди у полки могут оглянуться на уже отложенные книги. Алгоритму это не нужно: отложенная книга ни с одной оставшейся нужную сумму уже не даст.
Теперь то же самое точными словами.
Указательpointer · в Python — индекс
Переменная с номером позиции в списке. Слово «указатель» описывает роль переменной: её значение меняется по правилу алгоритма, и в любой момент по нему видно, какая часть списка уже обработана.
Два указателяtwo pointers · техника прохода
Техника, в которой два индекса двигаются по данным, и на каждом шаге сдвигается хотя бы один из них. Назад указатели не возвращаются, поэтому всего шагов не больше суммарной длины данных — время O(n), дополнительная память O(1).
Отсюда выигрыш по времени. Перебор всех пар списка длины n стоит n·(n − 1) / 2 проверок. Два указателя обходятся не больше чем n шагами, потому что каждый шаг навсегда исключает часть вариантов.
§6Три формы техники
Задачи на два указателя встречаются в трёх формах. Их различают по тому, откуда стартуют указатели и в какую сторону двигаются. Анимация показывает только движение, правила каждого хода разобраны в своих главах.
Старт с двух концов, указатели сходятся. Нужен порядок в данных: отсортированный список, строка для проверки палиндрома. Задача 1, разделение в главе 8.8.
Оба стартуют слева. r читает каждый элемент, w отстаёт и показывает, куда писать. Изменение списка на месте: задачи 2 и 3, перенос нулей.
По указателю на каждую последовательность, оба идут слева направо. Поиск подпоследовательности — глава 8.7, слияние отсортированных списков — занятие 31.
§7Карта модуля
Модуль идёт от того, как задачу формулируют и уточняют, к решению, доказательству, ошибкам и замерам. Главы 8.2 и 8.3 — про работу с условием, 8.4–8.8 — про сами алгоритмы, 8.9 и 8.10 — про проверку. Глава 8.11 собирает всё в решение одной задачи от начала до конца, 8.12 — практика и домашнее задание, 8.13 — тренажёр в формате собеседования.
- 8.2 Формулировки и признаки. Как звучат задачи и по каким словам в условии узнаётся техника.
- 8.3 Уточняющие вопросы. Что спросить до кода и что меняет каждый ответ.
- 8.4 Пара с заданной суммой. Перебор, правило указателей, ручной поиск пары, сборка функции из строк и счётчик проверок.
- 8.5 Почему указатели не пропускают ответ. Таблица всех пар и инвариант.
- 8.6 Код, крайние случаи и тесты. Построчный разбор, пустой вход, равные цены, тесты.
- 8.7 Указатели в одну сторону. Удаление повторов, сжатие последовательности, поиск подпоследовательности.
- 8.8 Разделение на две группы. Перенос нулей и разделение по порогу навстречу.
- 8.9 Типичные ошибки. Пошаговые прогоны ошибочных версий.
- 8.10 Замеры. Перебор, указатели, словарь и сортировка на списках до миллиона элементов.
- 8.11 Задача целиком. Новая задача от условия до проверки в порядке interview canvas, с ориентиром по минутам.
- 8.12 Практика и ДЗ. Стартовый набор
lesson_08, 37 тестов, шпаргалка. - 8.13 Мок-интервью. Восемь задач модуля по этапам секции: вопросы, примеры, выбор техники, код с тестами, прогон, секундомер.
§8Проверьте себя
Вопрос 1Почему у двух указателей время O(n), хотя пар в списке n·(n − 1) / 2?
Проверка за шаг одна: сумма двух элементов под указателями. Выигрыш в другом — в том, сколько пар исключается одним шагом.
Интерпретатор выполняет цикл одинаково при любых именах переменных. Число шагов определяется алгоритмом.
Верно. Указатели проходят список не больше одного раза, поэтому шагов не больше n. Каждый шаг исключает сразу много пар.
Указатели в задаче 1 стоят на двух концах списка и могут быть далеко друг от друга. Соседние элементы проверяются только в самом конце.
Вопрос 2Какая форма техники подходит для задачи «удалить из списка повторы, не создавая новый список»?
Верно.
rпроходит все элементы,wпоказывает место для следующего оставленного значения. Так работала и задача про спам в занятии 7.Указатели навстречу нужны, когда решение зависит от пары элементов с двух концов. Здесь каждый элемент нужно прочитать по порядку и решить, оставлять ли его.
Список здесь один, и результат остаётся в нём же. По двум спискам идут при слиянии.
Вопрос 3Что, по словам Яндекса, ждут от кандидата кроме работающего кода?
Верно: «ждём, что вы готовы обосновать, почему выбрали именно такие методы и знаете с какой сложностью они работают».
На странице сказано обратное: «не требуем досконального знания всех сигнатур методов».
На секцию отводится час на две задачи; журнал советует иметь решение первой примерно через полчаса.
- Яндекс. Алгоритмическое собеседование — yandex.ru/jobs/interview/algorithms
- Журнал Яндекс Образования. Алгоритмические собеседования в Яндексе: как подготовиться и чего ожидать — education.yandex.ru/journal
- Тренировки по алгоритмам от Яндекса. Лекция 5: «Префиксные суммы и два указателя» — youtube.com/watch?v=de28y8Dcvkg
- LeetCode. Top Interview 150 — leetcode.com/studyplan/top-interview-150; метки задач проверены по данным сайта 28.09.2026
- NeetCode. Two Pointers — neetcode.io/practice/problem-list/two-pointers
- Калинин П. Краткая теория про два указателя — algoprog.ru