Два указателя

Два индекса вместо повторного поиска

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

Простой пример — проверка, является ли массив палиндромом. Один указатель начинается слева, второй справа, а затем они движутся навстречу друг другу.

int left = 0;
int right = numbers.length - 1;
boolean palindrome = true;

while (left < right) {
    if (numbers[left] != numbers[right]) {
        palindrome = false;
        break;
    }

    left++;
    right--;
}

Каждый элемент участвует максимум в одной проверке пары, поэтому такой алгоритм работает за O(n) и использует O(1) дополнительной памяти.

Указатели могут двигаться по-разному

Два указателя не обязательно идут с разных концов. Иногда оба движутся слева направо: один читает элементы, а другой отмечает позицию, куда нужно записать следующий подходящий элемент. Такой вариант часто встречается при фильтрации данных прямо в исходном массиве.

int write = 0;

for (int read = 0; read < numbers.length; read++) {
    if (numbers[read] != 0) {
        numbers[write] = numbers[read];
        write++;
    }
}

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