Мы разобрали массивы и научились мерить скорость O-нотацией. Теперь возьмём самый частый приём, который превращает медленное решение в быстрое: два указателя. Идея простая — вместо двух вложенных циклов пройти по данным один раз, держа в них две подвижные метки.
Приём срабатывает не всегда, и главное здесь — научиться узнавать, когда он применим.
Проблема: вложенные циклы дорогие
Пусть в каталоге отсортированы цены и надо найти две позиции, дающие в сумме ровно номинал сертификата. Самое очевидное решение — перебрать все пары:
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
if (prices[i] + prices[j] == target) return new int[]{i, j};
}
}
Это O(N²). На тысяче позиций — около полумиллиона пар, ещё терпимо. На миллионе позиций — полтриллиона, то есть часы. А данные уже отсортированы, и мы этим никак не пользуемся.
Встречные указатели
Поставим одну метку в начало, другую в конец и посмотрим на сумму:
- сумма больше нужной — единственный способ её уменьшить — сдвинуть правую метку влево, к меньшим ценам;
- сумма меньше — двигаем левую метку вправо;
- совпало — ответ найден.
Метки идут навстречу: сумма больше цели — правая сдвигается влево, меньше — левая вправо. Пять шагов вместо пятнадцати пар полного перебора — ровно то, что печатает пример ниже.
Тот же проход целиком, с выводом каждой проверенной пары:
живой пример
class TwoPointers {
public static void main(String[] args) {
int[] prices = {4, 9, 15, 22, 30, 41};
int target = 37;
int left = 0;
int right = prices.length - 1;
int steps = 0;
while (left < right) {
steps++;
int sum = prices[left] + prices[right];
System.out.println(prices[left] + " + " + prices[right] + " = " + sum);
if (sum == target) break;
if (sum < target) left++;
else right--;
}
int pairs = prices.length * (prices.length - 1) / 2;
System.out.println("шагов: " + steps + ", пар при полном переборе: " + pairs);
}
}
Запустить
Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Неделя бесплатно →
Каждый шаг сдвигает одну из меток, и они движутся навстречу — значит, шагов не больше N. Получили O(N) вместо O(N²), без дополнительной памяти.
Почему это законно: сдвигая правую метку влево, мы отбрасываем все пары с этой ценой и любой левее — но все они дают сумму ещё больше, значит заведомо не подходят. На каждом шаге отбрасывается только заведомо ненужное — в этом вся суть приёма.
Обязательное условие — упорядоченность. На неотсортированных данных «сумма больше — двигаем правую метку» ничего не гарантирует: слева может лежать что угодно. Если порядка нет, приём не применим — там выручает хеш-таблица.
Попутные указатели
Второй вариант: обе метки идут в одну сторону, но с разной скоростью. Классический пример — убрать повторы в отсортированном массиве, ничего не выделяя дополнительно.
Медленная метка отмечает место, куда писать; быстрая читает подряд:
static int dedup(int[] codes) {
if (codes.length == 0) return 0;
int write = 0;
for (int read = 1; read < codes.length; read++) {
if (codes[read] != codes[write]) {
write++;
codes[write] = codes[read];
}
}
return write + 1;
}
Тот же приём с разной скоростью решает и задачу о цикле в связном списке: медленная метка шагает по одному узлу, быстрая по два. Если список замкнулся в кольцо, быстрая рано или поздно догонит медленную — расстояние между ними сокращается на шаг за итерацию. Если кольца нет, быстрая просто упрётся в конец.
Скользящее окно фиксированной ширины
Частный случай попутных указателей — когда между метками держат отрезок постоянной длины. Нужно найти наибольшую сумму k подряд идущих дней выручки.
Наивно — для каждого начала сложить k чисел: O(N·k). Но соседние окна отличаются всего двумя днями: один вошёл, один вышел. Значит, сумму не надо считать заново — её достаточно поправить:
long sum = 0;
for (int i = 0; i < k; i++) sum += revenue[i];
long best = sum;
for (int i = k; i < revenue.length; i++) {
sum += revenue[i] - revenue[i - k];
best = Math.max(best, sum);
}
O(N) и никакой дополнительной памяти. Типичная ошибка — начать с best = 0: если вся выручка отрицательная, ноль окажется «лучшим» ответом, которого на самом деле не существует.
Окно переменной ширины
Самый интересный вариант: ширина окна не задана, её диктует условие. Например, найти самый длинный отрезок ленты, в котором ни одна категория не повторяется.
Правый край всегда идёт вперёд и расширяет окно. Левый край подтягивается только тогда, когда условие нарушено — то есть когда встретился повтор. Окно на каждом шаге видно в выводе:
живой пример
import java.util.HashMap;
import java.util.Map;
class Window {
public static void main(String[] args) {
String feed = "abba";
Map<Character, Integer> last = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < feed.length(); right++) {
Integer seen = last.get(feed.charAt(right));
if (seen != null && seen >= left) {
left = seen + 1;
}
last.put(feed.charAt(right), right);
best = Math.max(best, right - left + 1);
System.out.println("окно: " + feed.substring(left, right + 1));
}
System.out.println("самый длинный отрезок без повторов: " + best);
}
}
Запустить
Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Неделя бесплатно →
Здесь спрятана самая частая ошибка приёма: левый край нельзя двигать назад. Проверка seen >= left именно об этом. На строке abba, дойдя до последней a, мы найдём её прошлое вхождение в самом начале — но окно к тому моменту уже начинается позже. Без проверки левый край откатился бы на позицию 1, окно стало бы bba и ответ вырос бы до трёх, хотя повтор внутри никуда не делся.
Хотя внутри есть вложенный while или прыжок левого края, время всё равно O(N): каждый край проходит массив максимум один раз, а суммарное число шагов обоих краёв не превышает 2N.
Как узнать приём в задаче
Признаки, по которым стоит вспомнить про два указателя:
- в условии есть слова «отрезок подряд», «подмассив», «подстрока» — почти наверняка окно;
- данные отсортированы, и ищется пара или тройка с нужным свойством — встречные указатели;
- надо переставить или отфильтровать элементы на месте, без дополнительной памяти — попутные указатели;
- наивное решение — два вложенных цикла, и при переходе к соседнему варианту пересчитывается почти то же самое.
И признак того, что приём не подойдёт: порядок элементов не важен либо ответ требует произвольного доступа к уже пройденным данным — тогда нужна хеш-таблица или префиксные суммы.
Как это сделано в Java
Сами приёмы из этой статьи пишут руками: готового «скользящего окна» в стандартной библиотеке нет и быть не может — его форма зависит от условия задачи. А вот то, по чему бегают указатели, давно написано и обкатано. И выбор хранилища здесь решает, останется решение линейным или незаметно станет квадратичным.
Эталонная реализация массива в Java — ArrayList. Внутри у него самый обычный массив, который подменяется на больший — примерно в полтора раза длиннее, — когда места перестаёт хватать. Поэтому get(i) стоит O(1), add в конец — O(1) амортизированно (редкий дорогой переезд размазывается по всем добавлениям), а вставка и удаление в середине — O(N): соседей приходится сдвигать.
Указателям нужен ровно доступ по индексу за O(1), так что по ArrayList они бегают с той же скоростью, что по массиву. А вот LinkedList для этого приёма — ловушка: он двусвязный, у концов всё O(1), но get(i) в середину идёт по ссылкам от края, то есть O(N). Цикл «два указателя по индексам» на нём молча превращается из O(N) в O(N²), хотя код выглядит буква в букву тем же. Подробнее про сам класс — в статье о связных списках.
Окну переменной ширины нужна ещё и память о том, что сейчас внутри окна. Тут берут HashMap или HashSet: доступ по ключу в среднем O(1), и общая оценка прохода не портится. Если ключи — символы или небольшие числа, вместо хеш-таблицы часто заводят простой массив-счётчик на 128 или 256 ячеек — тот же O(1), но без хеширования и упаковки в объекты.
Грабля живёт в попутных указателях «на месте». Соблазн сделать то же самое в ArrayList через remove(i) в цикле кончается плохо дважды. Во-первых, каждое удаление сдвигает весь хвост — это O(N) на операцию и O(N²) на проходе, ровно то, от чего мы уходили. Во-вторых, после удаления следующий элемент занимает освободившийся индекс, а счётчик цикла уже уехал вперёд — и этот элемент просто не проверяется, часть повторов остаётся в списке. Ошибка тихая: список стал короче, результат выглядит правдоподобно. Поэтому чистку и делают перезаписью: set(write, значение) не двигает ничего, а лишний хвост в конце отрезают одним subList(write, size()).clear().
Коротко
- Два указателя — две подвижные метки вместо двух вложенных циклов; типичный выигрыш O(N²) → O(N) без дополнительной памяти.
- Встречные метки идут навстречу и работают только на упорядоченных данных: на каждом шаге отбрасывается заведомо неподходящая часть.
- Попутные метки идут в одну сторону с разной скоростью: перезапись на месте, поиск цикла в списке.
- Скользящее окно фиксированной ширины правит сумму на краях вместо полного пересчёта.
- Окно переменной ширины расширяется правым краем и подтягивается левым при нарушении условия; левый край никогда не движется назад.
- Приём узнаётся по словам «отрезок подряд» в условии и по пересчёту почти одного и того же в наивном решении.
Что почитать дальше
- Префиксные суммы — что делать с суммой на отрезке, когда окно не скользит, а границы произвольны.
- Хеш-таблицы — запасной план, когда данные не отсортированы и встречные метки не работают.
- Монотонный стек — соседний приём одного прохода: ближайший больший элемент без вложенных циклов.
- Двоичный поиск по ответу — ещё один способ снести переборный цикл, когда ответ монотонен.