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

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

Один индекс стоит на первой ячейке, другой на последней. Вместе они задают кандидата на ответ.

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

Сравните результат с целью. Сравнение говорит, какой конец мешает.

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

Если она велика, сдвиньте правый индекс влево. Это единственный ход, который её уменьшит.

Цикл кончается, когда индексы встретились. Каждый элемент прочитан максимум один раз.

1. [2, 4, 5, 8, 11] lo=0 hi=4Цель равна 12. Указатели стартуют по краям.
2. 2 + 11 = 13Сумма на единицу больше цели. Уменьшить её может только правый конец.
3. [2, 4, 5, 8, 11] lo=0 hi=3Теперь 2 плюс 8 это 10, и этого мало. Увеличить может только левый конец.
4. [2, 4, 5, 8, 11] lo=1 hi=3Теперь 4 плюс 8 это 12. Цель достигнута точно.
5. ответ = [1, 3]Три сравнения на пять элементов. Ничего не прочитано дважды.

function twoPointers(arr, target) {
    let lo = 0;
    let hi = arr.length - 1;
    while (lo < hi) {
        const sum = arr[lo] + arr[hi];
        if (sum === target) return [lo, hi];
        if (sum < target) lo++;
        else hi--;
    }
    return null;
}

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

Контейнер с наибольшей водой

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

Площадь равна меньшей из линий, умноженной на расстояние между ними.

Начните с самой широкой пары, по линии на каждом краю.

Сдвигать более высокую линию бессмысленно: площадь ограничена низкой. Значит двигайте низкую и запоминайте лучшую площадь.

function maxArea(height) {
    let lo = 0;
    let hi = height.length - 1;
    let best = 0;

    while (lo < hi) {
        const area = Math.min(height[lo], height[hi]) * (hi - lo);
        best = Math.max(best, area);

        // the shorter side caps the area, so it is the only one worth moving
        if (height[lo] < height[hi]) lo++;
        else hi--;
    }

    return best;
}

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

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

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

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

• Скользящее окно (переменное) (Sliding window (variable)): Окно хранит живой отрезок, и оба конца идут вперёд. Эти указатели стартуют врозь и сходятся.
• Хеш-множество / словарь (Hash set / map): Хеш находит дополнение в неотсортированных данных ценой O(n) памяти. Указателям нужен порядок, но не память.
• Два указателя (в одну сторону) (Two pointers (same direction)): Там оба индекса идут вперёд: один читает, другой пишет. Здесь они сближаются с разных концов.
• Бинарный поиск (массив) (Binary search (array)): Бинарный поиск ищет одну фиксированную цель и делит отрезок пополам. Здесь сравниваемая пара меняется каждый шаг.

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

• Забывают, что вход обязан быть отсортирован

  Весь приём держится на порядке. На неотсортированных данных сравнение указывает не туда.

• Пишут lo <= hi

  Тогда индекс составит пару сам с собой. Для пары разных элементов нужно lo < hi.

• Двигают оба конца за один шаг

  Тогда верная пара может быть пропущена без проверки. Двигайте ровно один конец за шаг.

• Выдают одну тройку дважды

  После совпадения пропускайте равные значения с обеих сторон. Иначе дубликаты вернутся как разные ответы.

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

• Сумма двух II (отсортированный вход): Базовая форма: двигайте тот конец, что чинит сумму.
• Сумма трёх: Зафиксируйте одно значение и пустите два указателя по остатку.
• Контейнер с наибольшей водой: Двигайте низкую сторону, она ограничивает площадь.
• Проверка палиндрома: Сравните концы и шагните внутрь.
• Сбор дождевой воды: Двигайте сторону с меньшей стенкой и копите воду.
• Сортировка цветов: Два конца собирают нули и двойки.
• Квадраты отсортированного массива: Наибольший квадрат всегда лежит на одном из концов.

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

O(n)

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