Алгоритмы с нуля
Два указателя
У тебя есть массив и задача, что выглядит как два вложенных цикла — может, ты сравниваешь каждую пару элементов. Тогда кто-то показывает другой путь: используй два указателя вместо одного, начни с противоположных концов и иди к середине. Вложенный цикл исчезает. Однопроходный обход массива его заменяет. Вот техника двух указателей.
После этого урока ты сможешь узнавать, когда применяются два указателя, программировать два основных формата (противоположные концы и одно направление), разобраться, почему они превращают O(n²) в O(n), и решить классические задачи: проверить палиндром, найти две суммы в отсортированном массиве и убрать дубликаты на месте.
Техника двух указателей использует два индекса в массиве вместо одного. Мощь приходит из движения указателей по правилу: если условие истинно, двигай один; если ложно, двигай другой. Это правило делает работу вложенного цикла в однопроходном обходе.
Два основных формата:
1. Формат противоположных концов
Начни один указатель в начале (left = 0) и один в конце (right = arr.length - 1). Двигай их друг к другу:
let left = 0, right = arr.length - 1;
while (left < right) {
// Обработай arr[left] и arr[right]
// Двигай left или right по условию
if (condition) {
left++;
} else {
right--;
}
}Частое применение: проверить палиндром (совпадают ли концы?), или найти пару с суммой-целью (если пара мала, двигай left вправо; если велика, двигай right влево).
2. Формат одного направления (быстрый и медленный)
Начни оба указателя с начала. Один (медленный) продвигается осторожно; другой (быстрый) бежит вперёд:
let slow = 0, fast = 0;
while (fast < arr.length) {
// Двигай быстрый указатель
fast++;
// Условно двигай медленный
if (condition) {
slow++;
}
}Частое применение: убрать дубликаты из отсортированного массива на месте (медленный отмечает конец уникальных элементов; быстрый скользит вперёд и копирует новые уникальные значения назад в позицию медленного).
Почему это работает:
Наивный вложенный цикл проверяет каждую пару: для каждого i проверь все j, где j > i. Это O(n²).
Трюк двух указателей работает из-за инварианта: правило, что управляет движением указателей, гарантирует, что ты никогда не нужно перепроверять комбинацию. Для противоположных концов, когда left двигается вправо и right влево, зазор сужается; ты посещаешь каждую позицию ровно один раз. Для одного направления быстрый разведывает вперёд и передаёт находки медленному, что их записывает; опять же, однопроход, без возвращения назад.
Важное предусловие для противоположных концов два-сумма:
Если ты ищешь два элемента, что дают целевую сумму, используя противоположные концы, массив должен быть отсортирован. Без сортировки правило “двигай left, если сумма мала” не гарантирует, что найдёшь все пары. Два-сумма противоположных концов работает только на отсортированных данных.
Запрограммируем три классические задачи двух указателей:
1. Проверить палиндром (противоположные концы):
function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return false; // Несовпадение: не палиндром
}
left++;
right--;
}
return true; // Все пары совпали
}2. Два-сумма на отсортированном массиве (противоположные концы):
function twoSum(arr, target) {
// ПРЕДУСЛОВИЕ: arr должен быть отсортирован
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) {
return [left, right]; // Нашли пару
} else if (sum < target) {
left++; // Сумма мала, двигай left вправо
} else {
right--; // Сумма велика, двигай right влево
}
}
return null; // Пара не найдена
}3. Убрать дубликаты из отсортированного массива на месте (одно направление):
function removeDuplicates(arr) {
// ПРЕДУСЛОВИЕ: arr отсортирован
let slow = 0;
for (let fast = 1; fast < arr.length; fast++) {
if (arr[fast] !== arr[slow]) {
slow++;
arr[slow] = arr[fast]; // Скопируй уникальный элемент в позицию slow
}
}
return slow + 1; // Длина уникальных элементов
}Запусти эти функции:
Проследим противоположные концы два-сумма на [1, 3, 5, 7, 9] ища цель 12:
1
function twoSum(arr, target) {
2
let left = 0, right = arr.length - 1;
3
while (left < right) {
4
const sum = arr[left] + arr[right];
5
if (sum === target) return [left, right];
6
else if (sum < target) left++;
7
else right--;
8
}
9
return null;
10
}
Теперь проследим одно направление убрать дубликаты на [1, 1, 2, 2, 3]:
1
function removeDuplicates(arr) {
2
let slow = 0;
3
for (let fast = 1; fast < arr.length; fast++) {
4
if (arr[fast] !== arr[slow]) {
5
slow++;
6
arr[slow] = arr[fast];
7
}
8
}
9
return slow + 1;
10
}
Оба формата посещают каждый элемент ограниченное число раз:
| Задача | Время | Память | Замечания |
|---|---|---|---|
| Проверка палиндрома (противоположные концы) | O(n) | O(1) | Однопроход, два указателя |
| Два-сумма отсортированного массива (противоположные концы) | O(n) | O(1) | Требует отсортированный массив |
| Убрать дубликаты на месте (одно направление) | O(n) | O(1) | Меняет массив, возвращает новую длину |
| Перевернуть массив на месте (противоположные концы) | O(n) | O(1) | Менять концы, двигаться внутрь |
Почему O(n), не O(n²)?
Наивная проверка каждой пары — это O(n²): для каждого left, проверь все right.
Два указателя: left и right вместе посещают каждую позицию ровно один раз, когда они сходятся (противоположные концы) или когда быстрый разведывает и медленный записывает (одно направление). Нет вложенного цикла, однопроход через массив.
Почему алгоритм противоположных концов два-сумма требует отсортированный массив?
В алгоритме одного направления (быстрый/медленный) убрать дубликаты, почему быстрый бежит вперёд, пока медленный отмечает уникальные позиции?
Проверь палиндром '[1, 2, 3, 2, 1]'. Что вернёт isPalindrome? (1 = истина, 0 = ложь)
После вызова removeDuplicates на [5, 5, 5, 7, 7], сколько уникальных элементов?
В формате противоположных концов, когда left и right встретятся (left >= right), что это значит?
Частая ошибка
Применять противоположные концы два-сумма к неотсортированному массиву. Если массив [3, 1, 4, 2, 5] и ищешь сумму 6, используя противоположные концы, начни с 3 и 5 (сумма 8, велико). Двигай right влево на 2. Теперь 3 + 2 = 5 (мало). Двигай left на 1. Теперь 1 + 2 = 3 (всё ещё мало). Двигай left на 4. Теперь 4 + 2 = 6 (нашли!). Это сработало, но случайно. Правило “двигай left, если мало” не гарантирует корректность без сортировки. Алгоритм неправильный на неотсортированных данных.
Граничные случаи
Пустые или одноэлементные массивы. Если массив имеет 0 или 1 элемент, цикл противоположных концов while (left < right) никогда не входит (потому что 0 < 0 ложно, или 0 < 1 истинно только раз, но потом left++, right— сразу выходят). Для одного направления цикл for (let fast = 1; ...) начинает fast на 1; если массив один элемент (индекс 0), fast = 1 вне границ и цикл не запускается. Оба формата корректно обрабатывают пустые/одноэлементные массивы: они возвращают истину (палиндром) или вход неизменённым.
Почему техника двух указателей превращает O(n²) проблему вложенных циклов в O(n)?
Техника двух указателей использует два индекса и правило, чтобы решить проблемы в однопроходном обходе вместо вложенных циклов.
Ключевые факты:
-
Формат противоположных концов: Начни с обоих концов, двигайся к середине. Применяй, когда проверяешь симметрию (палиндром) или ищешь пары в отсортированном массиве.
-
Формат одного направления: Оба начинаются с начала; один разведывает вперёд, другой записывает. Применяй, когда меняешь массив на месте или когда ритм медленный/быстрый естественен.
-
Почему O(n), не O(n²)? Правило движения указателей гарантирует, что каждую позицию посещают максимум один раз за указатель, не один раз за внешний цикл. Нет вложенной итерации.
-
Противоположные концы два-сумма требует отсортированный вход. Без сортировки правило “двигай left, если сумма мала” неправильно.
-
Одно направление позволяет менять на месте. Быстрый находит; медленный пишет назад, перезаписывая дубликаты или старые значения.
Дальше ты будешь видеть два указателя, применённые к связным спискам (где обход — единственный способ вперёд) и скользящие окна (где два указателя отслеживают диапазон элементов под другим правилом).