Два указателя навстречу

Разберём задачу: в отсортированном массиве целых чисел нужно понять, есть ли два разных элемента с суммой target. Например, для [2, 7, 11, 15] и target = 9 ответ положительный: подходят 2 и 7.

Как использовать порядок при поиске пары

Нужно выбрать пару индексов i < j, для которой values[i] + values[j] == target. Важная часть условия — массив уже отсортирован по неубыванию. Именно порядок позволит не проверять каждую пару.

Почему проверка всех пар слишком дорога

Прямое решение фиксирует первый индекс i, затем перебирает каждый j > i. Оно проверяет n(n - 1) / 2 пар, поэтому работает за O(n²) времени и O(1) дополнительной памяти.

Перебор корректен даже без сортировки, но при n = 100 000 число пар уже измеряется миллиардами. Нужно использовать информацию о порядке.

Как перебор игнорирует сведения о соседях

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

Какая граница становится бесполезной после сравнения

Поставим left на минимальный, а right на максимальный ещё не исключённый элемент.

• Если сумма меньше target, элемент values[left] можно исключить. В паре с values[right] он уже дал максимально возможную для него сумму; с любым индексом левее right сумма будет не больше.
• Если сумма больше target, можно исключить values[right]. В паре с values[left] он уже дал минимально возможную для него сумму; с любым индексом правее left сумма будет не меньше.

Так одна проверка безопасно убирает хотя бы одну границу.

Где ещё может находиться подходящая пара

Перед каждой итерацией верно следующее: если среди ещё не рассмотренных элементов существует подходящая пара, оба её индекса находятся внутри [left, right].

Сдвиг выполняется только после доказательства, что удаляемая граница не может входить ни в одну подходящую пару. Поэтому инвариант сохраняется. Условие left < right не позволяет использовать один индекс дважды.

Сужаем диапазон с двух сторон

1. Если элементов меньше двух, вернуть false.
2. Установить left = 0, right = n - 1.
3. Пока left < right, вычислить сумму граничных элементов.
4. При равенстве target вернуть true.
5. Если сумма меньше target, увеличить left; иначе уменьшить right.
6. Если указатели встретились без успеха, вернуть false.

Встречные указатели без переполнения суммы

C++17

#include <cassert>
#include <iostream>
#include <vector>

bool hasPair(const std::vector<int>& values, long long target) {
    if (values.size() < 2) {
        return false;
    }

    std::size_t left = 0;
    std::size_t right = values.size() - 1;

    while (left < right) {
        const long long total = static_cast<long long>(values[left])
                              + static_cast<long long>(values[right]);

        if (total == target) {
            return true;
        }
        if (total < target) {
            ++left;
        } else {
            --right;
        }
    }

    return false;
}

int main() {
    assert(hasPair({2, 7, 11, 15}, 9));
    assert(hasPair({3, 3}, 6));
    assert(hasPair({-8, -3, 2, 5, 9}, 1));
    assert(!hasPair({1, 2, 4, 8}, 7));
    assert(!hasPair({}, 0));
    std::cout << "OK\n";
}

Python 3

def has_pair(values: list[int], target: int) -> bool:
    if len(values) < 2:
        return False

    left = 0
    right = len(values) - 1

    while left < right:
        total = values[left] + values[right]

        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1

    return False


assert has_pair([2, 7, 11, 15], 9)
assert has_pair([3, 3], 6)
assert has_pair([-8, -3, 2, 5, 9], 1)
assert not has_pair([1, 2, 4, 8], 7)
assert not has_pair([], 0)
print("OK")

Почему каждый указатель проходит массив один раз

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

Оценка предполагает, что вход уже отсортирован. Сортировка копии перед алгоритмом добавит O(n log n) времени и память под копию. В C++ элементы имеют тип int, а сумма вычисляется в long long, чтобы сложение двух int не переполнилось.

Два равных значения, отрицательные числа и края

• Пустой массив или один элемент: пары нет.
• Два одинаковых значения на разных индексах, например [3, 3]: это допустимая пара.
• Отрицательные числа: порядок и доказательство сдвига не меняются.
• Пара на самых краях массива.
• Большие по модулю int: сумму в C++ нужно расширить до сложения.

Проверяем пары в центре и на границах

• [2, 7, 11, 15], target = 9 → true.
• [3, 3], target = 6 → true: используются два индекса.
• [-8, -3, 2, 5, 9], target = 1 → true (-8 + 9).
• [1, 2, 4, 8], target = 7 → false.
• [], target = 0 → false.

Когда движение границы монотонно меняет сумму

Ищется пара в отсортированных данных, а изменение одной границы предсказуемо меняет значение: сдвиг left вправо не уменьшает сумму, сдвиг right влево не увеличивает её. В условии часто встречаются слова «пара», «отсортированный массив», «сумма» или «разность».

Почему несортированный вход разрушает доказательство

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

Какую сторону двигать при малой сумме

Вопрос. Почему при сумме меньше target нельзя вместо left сдвинуть right?

Ответ. values[right] — самый большой доступный партнёр для values[left], но даже с ним сумма мала. Уменьшение right сделает партнёра не больше и сумму — не больше. Нужно увеличить меньший элемент, то есть сдвинуть left.

Зачем требовать left < right

Вопрос. Почему цикл использует left < right, а не left <= right?

Ответ. При равенстве указателей оба слагаемых ссылались бы на один и тот же элемент. Условие требует два разных индекса, поэтому состояние left == right уже не содержит допустимой пары.

Прослеживаем сужение диапазона вручную

Задание. Вручную проследите алгоритм для [1, 2, 4, 7, 11] и target = 9. Записывайте (left, right, сумма) перед каждым сдвигом.

Подсказки. Начните с 1 + 11 = 12: сумма велика, поэтому убирается правая граница. Затем 1 + 7 = 8: сумма мала, поэтому сдвигается левая граница.

Проверка. Следующее состояние даёт 2 + 7 = 9, то есть ответ найден на индексах 1 и 3.

Самостоятельная задача о разности пары

Задача 1

Дан отсортированный по неубыванию массив и неотрицательное число difference. Определите, существуют ли два разных индекса, абсолютная разность значений на которых равна difference. Требуется O(n) времени и O(1) дополнительной памяти; приведите тесты для difference = 0.

Ускорение даёт доказанное исключение

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