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

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

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

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

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

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

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

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

Источники: Wikipedia (англ.): 3SUM

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 twoPointers(arr: number[], target: number): [number, number] | null {
    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;
}

def two_pointers(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

function twoPointers(array $arr, int $target): ?array {
    $lo = 0;
    $hi = count($arr) - 1;
    while ($lo < $hi) {
        $sum = $arr[$lo] + $arr[$hi];
        if ($sum === $target) return [$lo, $hi];
        if ($sum < $target) $lo++;
        else $hi--;
    }
    return null;
}

    public static int[] twoPointers(int[] arr, int target) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int sum = arr[lo] + arr[hi];
            if (sum == target) return new int[] { lo, hi };
            if (sum < target) lo++;
            else hi--;
        }
        return null;
    }

    public static int[] TwoPointers(int[] arr, int target) {
        int lo = 0;
        int hi = arr.Length - 1;
        while (lo < hi) {
            int sum = arr[lo] + arr[hi];
            if (sum == target) return new int[] { 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;
}

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

Паттерн «Два указателя (с концов)» нужен, когда в условии есть слова «отсортированный массив (или можно отсортировать)», «найти пару/тройку с заданной суммой» или «сжать с обоих концов (контейнер, площадь)». Решение на нём обычно укладывается в O(n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Два указателя (с концов)» чаще всего путают с этими паттернами: Скользящее окно (переменное), Хеш-множество / словарь, Два указателя (в одну сторону) и Бинарный поиск (массив).

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

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

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

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

• Пишут lo <= hi

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

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

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

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

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

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

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

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

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

У паттерна «Два указателя (с концов)» целевая сложность O(n).

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