Мы разобрали массивы и научились мерить скорость 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²). На тысяче позиций — миллион проверок, ещё терпимо. На миллионе позиций — триллион, то есть часы. А данные уже отсортированы, и мы этим никак не пользуемся.
Встречные указатели
Поставим одну метку в начало, другую в конец и посмотрим на сумму:
- сумма больше нужной — единственный способ её уменьшить — сдвинуть правую метку влево, к меньшим ценам;
- сумма меньше — двигаем левую метку вправо;
- совпало — ответ найден.
static int[] pairWithSum(int[] prices, int target) {
int left = 0;
int right = prices.length - 1;
while (left < right) {
int sum = prices[left] + prices[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++;
else right--;
}
return new int[]{-1, -1};
}
Каждый шаг сдвигает одну из меток, и они движутся навстречу — значит, шагов не больше 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: если вся выручка отрицательная, ноль окажется «лучшим» ответом, которого на самом деле не существует.
Окно переменной ширины
Самый интересный вариант: ширина окна не задана, её диктует условие. Например, найти самый длинный отрезок ленты, в котором ни одна категория не повторяется.
Правый край всегда идёт вперёд и расширяет окно. Левый край подтягивается только тогда, когда условие нарушено — то есть когда встретился повтор:
static int longestUnique(String feed) {
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);
}
return best;
}
Здесь спрятана самая частая ошибка приёма: левый край нельзя двигать назад. Проверка seen >= left именно об этом. На строке abba, дойдя до последней a, мы найдём её прошлое вхождение в самом начале — но окно к тому моменту уже начинается позже, и откат назад дал бы неверный ответ.
Хотя внутри есть вложенный while или прыжок левого края, время всё равно O(N): каждый край проходит массив максимум один раз, а суммарное число шагов обоих краёв не превышает 2N.
Как узнать приём в задаче
Признаки, по которым стоит вспомнить про два указателя:
- в условии есть слова «отрезок подряд», «подмассив», «подстрока» — почти наверняка окно;
- данные отсортированы, и ищется пара или тройка с нужным свойством — встречные указатели;
- надо переставить или отфильтровать элементы на месте, без дополнительной памяти — попутные указатели;
- наивное решение — два вложенных цикла, и при переходе к соседнему варианту пересчитывается почти то же самое.
И признак того, что приём не подойдёт: порядок элементов не важен либо ответ требует произвольного доступа к уже пройденным данным — тогда нужна хеш-таблица или префиксные суммы.
Коротко
- Два указателя — две подвижные метки вместо двух вложенных циклов; типичный выигрыш O(N²) → O(N) без дополнительной памяти.
- Встречные метки идут навстречу и работают только на упорядоченных данных: на каждом шаге отбрасывается заведомо неподходящая часть.
- Попутные метки идут в одну сторону с разной скоростью: перезапись на месте, поиск цикла в списке.
- Скользящее окно фиксированной ширины правит сумму на краях вместо полного пересчёта.
- Окно переменной ширины расширяется правым краем и подтягивается левым при нарушении условия; левый край никогда не движется назад.
- Приём узнаётся по словам «отрезок подряд» в условии и по пересчёту почти одного и того же в наивном решении.
Дальше — префиксные суммы: что делать, когда отрезки нужны не подряд, а произвольные, и запросов много.