Два указателя (в одну сторону)

Два указателя (в одну сторону): как это работает?

Оба индекса стартуют с начала массива. read читает, а write помечает следующее место записи.

read сдвигается на каждом шаге цикла. Он смотрит каждый элемент ровно один раз.

Проверка решает, оставить ли текущее значение. Только эта проверка и меняется от задачи к задаче.

При сохранении значение копируется в ячейку write. После этого write сдвигается на один.

При отбрасывании write стоит на месте. Ячейка ждёт следующее выжившее значение.

write отстаёт от read ровно на число отброшенных. Поэтому начало массива до write и есть ответ.

1. [3, 2, 3, 4, 2] write=0Убираем все тройки. arr[0] это тройка, поэтому запись не идёт.
2. [2, 2, 3, 4, 2] write=1arr[1] это двойка, она остаётся. Значение уходит в ячейку 0.
3. [2, 2, 3, 4, 2] write=1arr[2] это ещё одна тройка. write остаётся на месте.
4. [2, 4, 3, 4, 2] write=2arr[3] это четвёрка, она остаётся. Значение ложится в ячейку 1.
5. [2, 4, 2, 4, 2] write=3Последняя двойка ложится в ячейку 2. Ответ это длина 3.

function compact(arr) {
    let slow = 0;
    for (let fast = 0; fast < arr.length; fast++) {
        if (shouldKeep(arr[fast], arr[slow])) {
            arr[slow] = arr[fast];
            slow++;
        }
    }
    return slow; // new length
}

Два указателя (в одну сторону): разбор примера

Оставить каждое значение не более двух раз

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

Работайте в том же массиве и верните новую длину.

Первые два значения проходят всегда, две копии разрешены.

Дальше оставляйте arr[read], только если оно отличается от arr[write - 2]. В той ячейке лежит уже записанная вторая копия.

function removeDuplicatesII(nums) {
    let write = 0;

    for (let read = 0; read < nums.length; read++) {
        // nums[write - 2] is the copy two slots back in the output
        if (write < 2 || nums[read] !== nums[write - 2]) {
            nums[write] = nums[read];
            write++;
        }
    }

    return write; // new logical length
}

Два указателя (в одну сторону): когда применять?

Эти формулировки в условии ведут сюда:

• •удалить дубликаты на месте, сохранив порядок
• •переместить/разбить элементы с сохранением порядка
• •сжать массив, используя O(1) дополнительной памяти
• •сдвинуть нули или заданное значение в конец

Два указателя (в одну сторону): с чем путают?

• Преобразование массива на месте (In-place array transform): Работа в одном буфере это цель. Отстающий указатель записи это один из способов её достичь.
• Два указателя (с концов) (Two pointers (opposite ends)): Те указатели стартуют по краям отсортированных данных и сходятся. Эти оба стартуют с нулевого индекса.
• Скользящее окно (переменное) (Sliding window (variable)): Окно тоже двигает два индекса вперёд, но хранит живой отрезок. Здесь отстающий индекс это место записи.
• Быстрый и медленный указатели (Fast & slow pointers): Там быстрый указатель делает два шага и ловит цикл. Здесь он делает один и читает.

Два указателя (в одну сторону): частые ошибки

• Дают write обогнать read

  Тогда копия затрёт данные, которые read ещё не видел. write двигается только при сохранении.

• Проверяют по исходному массиву

  Проверка идёт по arr[write - 1], последнему сохранённому значению. arr[read - 1] может быть уже затёрт.

• Сдвигают хвост при каждом удалении

  Линейный проход превращается в O(n в квадрате). Хватает одного копирования вперёд.

• Верят ячейкам после write

  Там лежат старые значения, оставшиеся до прохода. Смысл имеют только первые write ячеек.

Два указателя (в одну сторону): задачи с собеседований

• Удаление дубликатов из отсортированного массива: Оставляйте значение, только если оно отличается от arr[write - 1].
• Удаление элемента: Оставляйте всё, что не равно заданному значению.
• Сдвиг нулей: Скопируйте ненулевые вперёд, потом добейте хвост.
• Удаление дубликатов из отсортированного массива II: Проверка смотрит на две ячейки назад, а не на одну.
• Сжатие строки: Запишите символ, потом запишите длину его серии.
• Является ли подпоследовательностью: Один указатель идёт по короткой строке, другой по длинной.
• Слияние отсортированных массивов: Пишите с конца, тогда непрочитанное не затрётся.

Два указателя (в одну сторону): сложность по времени и памяти

O(n)

n до 1e6 даёт O(n) времени и O(1) памяти. Указатель чтения видит каждый элемент один раз.