1. Что такое two pointers и почему “pointers” — это не страшно
Если вы впервые слышите “two pointers”, мозг может нарисовать себе страшные “указатели из C”, память, адреса и прочие ужасы из легенд программистского фольклора. На самом деле в задачах на массивы pointers — это почти всегда просто два индекса типа Int: left и right (или read и write). Мы не лезем в память напрямую, мы аккуратно двигаемся по массиву, соблюдая границы.
Two pointers — это не одна конкретная задача, а повторяемая схема мышления. И обычно она включается, когда вы видите наивное решение с двумя вложенными циклами: “для каждого элемента… поискать пару…” или “для каждого старта… пересчитать отрезок…”. Часто это можно переписать в один проход, если вы умеете держать два индекса и правило их движения.
Чтобы не звучало как “верь мне, я видел такое во сне”, давайте сразу зафиксируем два основных “подвида” two pointers в виде таблицы:
| Сценарий | Как выглядят индексы | Для чего | Примерный инвариант |
|---|---|---|---|
| left/right (границы) | |
пары, развороты, проверки “с концов”, границы отрезка | всё снаружи [left...right] уже “не нужно” или “обработано” |
| read/write (чтение/запись) | |
сжатие массива, удаление элементов, удаление дублей | array[0..<write] — уже собранный корректный результат |
Оба сценария — two pointers, просто “вторая рука” у вас делает разную работу.
2. Инвариант: как доказать себе, что вы не “просто двигаете индексы”
В программировании очень легко написать код, который “вроде работает на примерах”, но при первой же нетипичной ситуации разваливается. Two pointers особенно любят такие провалы: один неверный +1, одна неправильная граница — и вы либо пропускаете ответ, либо улетаете в Index out of range, либо (самое весёлое) получаете бесконечный цикл. Поэтому нам нужен простой инструмент самоконтроля: инвариант.
Инвариант — это утверждение, которое должно оставаться истинным на каждом шаге алгоритма. Это как правило дорожного движения: если вы его держите, вы не въедете в стену… ну, по крайней мере, не из-за индексов. В two pointers инвариант обычно отвечает на вопрос: какую часть массива мы уже “закрыли” и почему туда не нужно возвращаться.
Давайте на мини-схеме покажем типичный “left/right” сценарий:
flowchart LR
A[0] --- B[1] --- C[2] --- D[3] --- E[4] --- F[5]
L((left)) -.-> B
R((right)) -.-> E
subgraph Window["Текущая зона внимания"]
B --- C --- D --- E
end
Смысл: “окно внимания” между left и right — это то, что ещё может дать ответ. Всё вне окна мы уже исключили (по причине, которую мы должны уметь объяснить словами).
И здесь появляется ключевое правило, которое спасает вас от вечных циклов: на каждой итерации должен двигаться хотя бы один индекс. Если ни left, ни right не меняются — вы застряли. В жизни это называется “залип”, в коде это называется while true, но без смысла.
3. Разворот массива “на месте” как разогрев
Перед задачами на пары и суммы полезно потрогать two pointers руками в максимально понятной форме: когда у вас есть два конца и вы идёте к центру. Разворот массива — идеальный пример, потому что в нём почти невозможно “потерять смысл”: вы меняете местами элементы, пока индексы не встретятся.
Сначала — функция (обратите внимание на inout: мы меняем массив “на месте”, без создания второго):
import Foundation
func reverseInPlace(_ numbers: inout [Int]) {
guard numbers.count > 1 else { return }
var left = 0
var right = numbers.count - 1
while left < right {
numbers.swapAt(left, right)
left += 1
right -= 1
}
}
Инвариант здесь звучит почти как заклинание: “всё левее left и всё правее right уже стоит на правильных местах после разворота”. И мы движемся к центру, не откатываясь назад.
Чтобы встроить это в наш общий учебный “мини‑проект” (консольный файл, где мы пробуем алгоритмы), добавим очень простую подготовку входа: чтение массива чисел из одной строки.
import Foundation
func parseIntArray(_ line: String) -> [Int] {
line.split(separator: " ").compactMap { Int($0) }
}
И мини-запуск (top-level код, как в ранних днях курса):
let numbers = parseIntArray(readLine() ?? "")
var copy = numbers
reverseInPlace(©)
print("original:", numbers)
print("reversed:", copy)
Да, это “учебная песочница”, но она полезна: вы можете быстро менять ввод и видеть поведение функций.
4. Поиск пары с суммой в отсортированном массиве
Сейчас будет классика: задача “two sum”, но с важным условием — массив отсортирован. Именно сортировка даёт нам правило движения указателей. Если массив не отсортирован, то “сдвинуть left или right” становится гаданием на кофейной гуще, а не алгоритмом.
Постановка: дан отсортированный массив numbers и target. Найти индексы двух разных элементов, сумма которых равна target. Если нет — вернуть nil. И сразу фиксируем контракт: возвращаем именно индексы, не значения. Поэтому сигнатура — (Int, Int)?.
import Foundation
func twoSumSorted(_ numbers: [Int], target: Int) -> (Int, Int)? {
guard numbers.count >= 2 else { return nil }
var left = 0
var right = numbers.count - 1
while left < right {
let sum = numbers[left] + numbers[right]
if sum == target { return (left, right) }
if sum < target {
left += 1
} else {
right -= 1
}
}
return nil
}
Почему это работает (простыми словами). Если сумма слишком маленькая, то элемент слева “слишком маленький”, и чтобы увеличить сумму, логично сдвинуть left вправо (в отсортированном массиве там значения не уменьшатся). Если сумма слишком большая, мы уменьшаем её, двигая right влево. Это и есть правило движения.
Инвариант можно сформулировать так: “все пары, которые используют элементы левее left или правее right, уже точно не могут дать target (потому что мы их исключили монотонным правилом)”.
Добавим небольшой запуск в наш файл, чтобы функция была не “в вакууме”:
let numbers = parseIntArray(readLine() ?? "")
let target = Int(readLine() ?? "") ?? 0
if let (i, j) = twoSumSorted(numbers, target: target) {
print("pair:", i, j) // например: pair: 1 4
print("values:", numbers[i], numbers[j])
} else {
print("no pair")
}
Здесь важно помнить: если вход не отсортирован, вы получите “случайный театр”. Поэтому либо сортируйте заранее (но сортировка — это отдельная стоимость), либо честно называйте функцию twoSumSorted, как мы сделали.
5. Условие на сумму: не только равенство, но и “не больше”
Когда вы освоили “сумма равна target”, следующий естественный шаг — задачи, где нужно не найти конкретную пару, а посчитать или проверить условие вида “сумма не больше лимита”. И здесь two pointers тоже работают очень красиво — опять же, на отсортированном массиве.
Рассмотрим задачу: посчитать количество пар (i, j), i < j, таких что numbers[i] + numbers[j] <= limit. Это полезный тип задач: он встречается в оптимизациях, в статистике, в “сколько комбинаций проходит фильтр”.
Код будет коротким, но идея — не самая очевидная на первый взгляд:
import Foundation
func countPairsWithSumAtMost(_ numbers: [Int], limit: Int) -> Int {
guard numbers.count >= 2 else { return 0 }
var left = 0
var right = numbers.count - 1
var count = 0
while left < right {
let sum = numbers[left] + numbers[right]
if sum <= limit {
count += (right - left)
left += 1
} else {
right -= 1
}
}
return count
}
Почему count += (right - left) — это не магия. Если numbers[left] + numbers[right] <= limit, то из-за сортировки все элементы между left и right (то есть left+1 ... right) тоже образуют с left сумму не больше лимита, потому что они не больше numbers[right]. Значит, мы одним шагом добавляем сразу пачку пар и двигаем left.
Инвариант: “все пары с первым индексом меньше текущего left уже полностью учтены; right указывает максимальную правую границу, которая ещё может давать валидные пары с текущим left”.
6. Read/write: “сжать массив” без второго массива
После “двух концов” пора увидеть второй главный стиль two pointers: read и write. Он особенно любим в задачах “удалить элементы”, “оставить только уникальные”, “переместить все нули в конец”. Психологически это похоже на работу редактора: вы читаете исходный текст и пишете “чистовик” в тот же лист, просто аккуратно.
Важно понять роль write: это индекс следующей позиции записи. То есть то, что лежит в 0..<write, уже является готовым результатом (инвариант!), а write — место, куда мы положим следующий “хороший” элемент.
Удаляем нули: move zeros to end
Задача: переставить элементы так, чтобы все нули оказались в конце, сохранив относительный порядок ненулевых. Это прямо классика read/write.
import Foundation
func moveZerosToEnd(_ numbers: inout [Int]) {
var write = 0
for read in 0..<numbers.count {
if numbers[read] != 0 {
numbers.swapAt(read, write)
write += 1
}
}
}
Инвариант здесь простой и очень практичный: numbers[0..<write] — уже ненулевые элементы в правильном порядке. Мы читаем очередной элемент и, если он “хороший”, двигаем его в зону результата.
Да, тут есть swapAt, и иногда read == write, тогда swap “меняет элемент сам с собой”. Это нормально: Swift не обидится.
Удаляем дубликаты в отсортированном массиве
Теперь чуть тоньше: дан отсортированный массив, нужно вернуть массив без дублей. Это снова read/write, но уже без свопов: мы будем переписывать значения.
import Foundation
func uniqueSorted(_ numbers: [Int]) -> [Int] {
guard !numbers.isEmpty else { return [] }
var buffer = numbers
var write = 1
for read in 1..<buffer.count {
if buffer[read] != buffer[write - 1] {
buffer[write] = buffer[read]
write += 1
}
}
return Array(buffer[0..<write])
}
Обратите внимание на маленькую, но важную деталь: сравнение идёт с buffer[write - 1]. Это “последний записанный уникальный элемент”. То есть мы сравниваем не с “предыдущим прочитанным”, а с “предыдущим сохранённым”. Если держать в голове эту роль, код перестаёт быть загадкой.
Инвариант: buffer[0..<write] всегда содержит уникальные элементы (без дублей) из уже обработанной части массива.
7. Two pointers для отрезков: границы, которые “едут” к центру
Слово “отрезок” (подмассив) иногда звучит как что-то из школьной геометрии: “отрезок AB”, “длина”, “точка”. На практике в массивах отрезок — это просто непрерывный диапазон индексов, и two pointers часто становятся двумя движущимися границами этого отрезка. Это похоже на то, как вы двумя пальцами на телефоне выделяете часть текста: один палец — левая граница, второй — правая.
Внутри этой лекции мы не будем уходить в полноценные “окна” со сложными условиями и пересчётами (это отдельная большая тема), но важно увидеть идею: границы отрезка — это тоже two pointers. Даже если вы пока делаете что-то простое: развернуть только часть массива, проверить “зеркальность”, отфильтровать диапазон.
Например, развернуть элементы только на отрезке [l...r] (включая границы), при этом сам отрезок задаётся извне. Это тоже two pointers, только границы стартуют не с концов массива.
import Foundation
func reverseSegment(_ numbers: inout [Int], from l: Int, to r: Int) {
guard l >= 0, r < numbers.count, l < r else { return }
var left = l
var right = r
while left < right {
numbers.swapAt(left, right)
left += 1
right -= 1
}
}
Инвариант тот же, что и при полном развороте, просто “мир” ограничен отрезком: всё внутри “сжимается к центру”, а снаружи мы вообще ничего не трогаем.
И вот здесь уже начинает чувствоваться “мышление границами”: мы заранее проверяем корректность l и r через guard, чтобы не превращать урок алгоритмов в урок “как ловить out-of-range”.
Памятка: схема для left/right
Когда two pointers только появляются в вашем коде, мозг часто пытается держать всё сразу: “когда двигаем left?”, “когда двигаем right?”, “а если равны?”, “а если не нашли?”. Это нормально: это ровно тот момент, когда программист в голове рисует ментальную модель.
Чтобы облегчить этот момент, полезно держать перед глазами универсальную блок‑схему для left/right сценария (она не решает задачу за вас, но заставляет задать правильные вопросы):
flowchart TD
A[Инициализируем left и right] --> B{left < right?}
B -- нет --> Z[Стоп: ответа нет / цикл завершён]
B -- да --> C[Считаем метрику: sum / сравнение / проверка]
C --> D{Условие выполнено?}
D -- да --> E[Возвращаем ответ / обновляем лучший]
D -- нет --> F{Кого двигать и почему?}
F -->|двигаем left| G[left += 1]
F -->|двигаем right| H[right -= 1]
G --> B
H --> B
Ключевой блок тут — “Кого двигать и почему?”. Если вы не можете ответить на него словами (без кода), значит, вы ещё не нашли правило движения, и лучше не писать while, пока не нашли.
8. Типичные ошибки
Ошибка №1: условие left <= right там, где нужен left < right.
В задачах на пару элементов обычно нельзя использовать один и тот же элемент дважды, поэтому left и right должны указывать на разные позиции. Условие left <= right легко приводит к тому, что вы “разрешаете” пару из одного элемента (особенно если дальше в коде появится невнимательная проверка). Если задача именно про пару, держите left < right как правило по умолчанию.
Ошибка №2: индексы не двигаются в одной из веток, и цикл становится бесконечным.
Это классический баг: вы написали while left < right, посчитали sum, обработали пару условий, а в ветке “ничего не подошло” забыли left += 1 или right -= 1. На тесте с “удачным” вводом всё работает, а на “неудачном” программа зависает. Привычка простая: после написания цикла глазами проверьте, что в каждой ветке кто-то двигается.
Ошибка №3: two pointers применяют без предпосылок, которые делают правило движения корректным.
Например, twoSumSorted работает именно потому, что массив отсортирован, и сдвиг left действительно “увеличивает левый элемент”, а сдвиг right “уменьшает правый”. Если массив не отсортирован, такое правило превращается в лотерею. Лечится честным контрактом: либо сортируете вход, либо называете функцию так, чтобы условие было очевидно.
Ошибка №4: путают, что возвращают — индексы или значения.
В задачах на пары половина ошибок происходит не в алгоритме, а в “контракте”: студент возвращает (numbers[left], numbers[right]), а потом использует результат как индексы, или наоборот. Хорошая привычка — фиксировать это прямо в сигнатуре и имени: (Int, Int)? как индексы, или кортеж с метками, если возвращаете значения.
Ошибка №5: в read/write неправильно понимают роль write.
write — это не “последний записанный”, а “позиция следующей записи”. Поэтому сравнение часто идёт с write - 1, а не с write. Если помнить, что 0..<write — уже готовый результат, код начинает читаться как нормальная история, а не как случайный набор индексов.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ