Обзор

Метод двух указателей позволяет решать задачи на коллекциях за один проход, синхронно управляя границами или независимыми индексами. Этот подход незаменим для оптимизации работы с отсортированными массивами и поиска подстрок.

Идея паттерна

Указатель - это переменная, хранящая индекс или позицию в структуре данных (массиве, строке или связанном списке). В то время как обычные алгоритмы используют один указатель для итерации, введение второго указателя открывает новые возможности: мы можем сравнивать элементы в разных позициях и перемещать один или оба указателя в зависимости от логики задачи.

Там, где "наивный" подход требует вложенных циклов со сложностью O(n²), два указателя часто позволяют достичь линейной сложности O(n) по времени и O(1) по дополнительной памяти. Особенно эффективно это работает на отсортированных данных: движение указателя дает предсказуемый результат (значение либо увеличится, либо уменьшится), что избавляет от лишних проверок.

Типичные сценарии

Паттерн применим для широкого круга задач:

• Поиск парных значений: например, поиск суммы в отсортированном массиве.
• Сдвиг границ подмассива: поиск минимума или соблюдение условий.
• Модификация "на месте": разделение коллекции по условию или удаление дубликатов без выделения новой памяти.
• Реверс или обмен элементов: например, разворот строки или проверка на палиндром.
• Слияние двух структур: объединение отсортированных массивов.

Такие подходы, как "быстрый и медленный указатели" (алгоритм черепахи и зайца) и "скользящее окно" (sliding window), являются логическим развитием этой идеи.

Стратегии движения указателей

Может быть несколько разных стратегий перемещения указателей:

1. Снаружи внутрь: указатели движутся от краев массива навстречу друг другу. Эта стратегия лежит в основе эффективного поиска парных элементов в задаче о "сумме двух" и сжатия границ в задаче о "контейнере с водой".

2. Изнутри наружу: два указателя стартуют из центра и расходятся к краям. Это классика для задачи поиска самого длинного палиндрома. Здесь сложно не вспомнить Ричарда Хендрикса из "Кремниевой долины" и его идею оптимизации, которая хоть и относилась к сжатию данных, но отлично иллюстрировала принцип движения изнутри наружу.

3. Однонаправленное перемещение: оба указателя стартуют с одного конца и движутся в одном направлении. Часто используется в "скользящем окне" для поддержания интервала данных.

4. Поэтапное перемещение: один указатель ("быстрый") итерирует коллекцию, а другой ("медленный") сдвигается только при выполнении определенного условия. Идеально для фильтрации элементов на месте или поиска циклов в списках.

Когда использовать

Есть несколько признаков в условии задачи, которые могут указывать на применимость паттерна:

1. Работа с линейными структурами данных. Если в задаче фигурирует массив, строка или связанный список, велика вероятность, что два указателя помогут оптимизировать обход.

2. Массив уже отсортирован. Если данные упорядочены, два указателя позволяют избежать полного перебора пар. Благодаря сортировке мы заранее знаем, в какую сторону двигать указатель, чтобы увеличить или уменьшить текущую сумму/значение.

3. Модификация "на месте". Если нельзя использовать дополнительную память и нужно изменить текущий массив (удалить дубликаты, переставить элементы, развернуть), может сработать паттерн двух указателей. Один указатель будет "читать" данные, а другой - "записывать" в нужные позиции.

4. Поиск подмассива. Когда нужно найти отрезок (подмассив или подстроку), удовлетворяющий условию (максимальная длина, сумма, количество уникальных символов). Здесь указатели будут определять левую и правую границы этого отрезка.

5. Сравнение элементов. Если задача требует сопоставить элементы внутри одного массива (проверка на палиндром) или в двух разных отсортированных массивах (слияние, поиск пересечений).

Два указателя или хеш-таблицы

Часто возникают ситуации, когда условия задачи позволяют использовать как два указателя, так и хеш-таблицы. В этом случае выбор может быть неочевидным и будет зависеть от баланса между скоростью, памятью и состоянием данных. Чтобы принять верное решение, нужно проверить, чем именно мы готовы пожертвовать в конкретной ситуации.

1. Память. Это первое, на что стоит обратить внимание.

   • Два указателя: паттерн работает "на месте", дополнительная память O(1).
   • Хеш-таблица: требует место для хранения ключей и значений, дополнительная память O(n).

2. Состояние данных. Наличие сортировки.

   • Два указателя: в большинстве сценариев, таких как поиск пар и сумм, требуют, чтобы данные были отсортированы. Если придется добавить этап сортировки, это может замедлить общее решение.
   • Хеш-таблица: порядок не важен, подходит для неупорядоченных данных.

3. Сохранение контекста.

   • Два указателя: информация о взаимном расположении элементов, лучше подходят для поиска интервалов, подстрок или работы с границами.
   • Хеш-таблица: информация о факте наличия, лучше подходит для быстрого поиска и проверки вхождений элементов.

Таким образом, если задачу можно решить обоими способами - выбирайте два указателя, если вам важна память и массив уже отсортирован. Выбирайте хеш-таблицу, если данные не упорядочены и вы не хотите тратить время на их сортировку.

Примеры

1. Реверс массива

Рассмотрим задачу реверса массива Reverse String.

В этой простой задаче отлично видно, как работают два указателя. Они движутся снаружи внутрь, и на каждом шаге выполняется обмен символов. Когда указатели встретились, цикл останавливается.

Шаг 1.

Шаг 2.

Шаг 3.

Вот как это выглядит в коде:

function reverseString(s) {
  let i = 0;
  let j = s.length - 1;
  while (i < j) {
    [s[i], s[j]] = [s[j], s[i]];
    i++;
    j--;
  }
}

2. Проверка на палиндром

Еще один пример - задача проверки строки на палиндром Valid Palindrome.

Наивный и неэффективный (за квадратичное время O(n²)) подход к решению - это использовать два вложенных цикла.

Для эффективного решения мы можем использовать подход двух указателей. Один указатель будет идти по строке с начала, а второй - с конца. На каждом шаге мы будем сравнивать символы. Если они будут отличаться на каком-то шаге, то строка не является палиндромом. Если два указателя встретились, то останавливаем цикл и возвращаем ответ, что строка является палиндромом.

В таком подходе мы полагаемся на свойство палиндромов - симметрию. Это позволяет нам сравнить все символы в одном проходе и получить решение с линейной сложностью O(n).

Иллюстрация работы этого подхода на строке "racecar":

Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Вот как это выглядит в коде:

function isPalindrome(s) {
  let i = 0;
  let j = s.length - 1;
  while (i < j) {
    while (i < j && !isLetterOrDigit(s[i])) {
      i++;
    }
    while (i < j && !isLetterOrDigit(s[j])) {
      j--;
    }
 
    if (s[i].toLowerCase() !== s[j].toLowerCase()) {
      return false;
    }
 
    i++;
    j--;
  }
  return true;
}
 
function isLetterOrDigit(char) {
  return (
    (char >= "0" && char <= "9") ||
    (char >= "a" && char <= "z") ||
    (char >= "A" && char <= "Z")
  );
}

Выше в коде мы еще дополнительно продвигаем каждый указатель, пока его текущий символ не является буквой или цифрой. Это нужно для выполнения условий задачи - так как пробелы, знаки препинания и другие символы в строке не должны учитываться.

Итоги

Подводя итог, паттерн двух указателей - это не просто алгоритмический трюк, а мощный способ оптимизации. По своей сути, это применение стратегии поиска с отсечением, когда на каждом шаге мы имеем возможность безопасно отсечь - исключить множество не подходящих решений.

Умение вовремя распознать признаки этого подхода и грамотно сопоставить его с альтернативами, такими как хеш-таблицы, отличает опытного инженера от новичка.

Дальше - больше: мы разберем серию задач на "два указателя" и на реальных сценариях покажем, как именно работает этот паттерн.