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

От перебора к короткому примеру

Проверка всех пар требует O(n²). Если массив отсортирован, начинаем с крайних элементов: при слишком маленькой сумме можно исключить весь левый элемент, при слишком большой — весь правый. Ищем два разных индекса с заданной суммой.

Инвариант

Если подходящая пара ещё существует, оба её индекса лежат в [left, right]. При a[left] + a[right] < target любая пара текущего left с меньшим правым индексом тоже слишком мала. Симметрично при слишком большой сумме исключается right.

1. a = [1, 2, 4, 7], target = 6. Крайняя пара 1 + 7 = 8: уменьшаем right.
2. 1 + 4 = 5: увеличиваем left. Теперь 2 + 4 = 6 — ответ найден.
3. Если left >= right, различных индексов больше нет: возвращаем false.

Код на C++ и Python

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

#include <vector>

bool has_pair(const std::vector<int>& a, long long target) {
    int left = 0;
    int right = static_cast<int>(a.size()) - 1;
    while (left < right) {
        long long sum = static_cast<long long>(a[left]) + a[right];
        if (sum == target) return true;
        if (sum < target) {
            ++left;
        } else {
            --right;
        }
    }
    return false;
}

def has_pair(a, target):
    left, right = 0, len(a) - 1
    while left < right:
        total = a[left] + a[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
    return False

Проверьте контракт

• [] и target = 6 → false
• [3] и target = 6 → false
• [3, 3] и target = 6 → true
• [-4, -1, 2, 7] и target = 3 → true

Сложность и ограничения метода

• Не сортируем внутри примера: sorted input — предусловие. Указатели делают суммарно не больше n − 1 сдвигов: O(n) времени и O(1) дополнительной памяти. Если нужна сортировка, добавить её стоимость; исходные индексы при этом меняются.
• В одном направлении read/write подходят для уплотнения массива; left/right — для окна. Fast/slow в списке используется, например, для цикла и требует отдельного доказательства, а не аргумента суммы.
• На неотсортированном массиве сдвиг по сумме небезопасен. Если нужны исходные индексы без сортировки, рассмотрите хеширование. При фиксированной разрядности ключей оно может дать ожидаемое линейное время, но использует дополнительную память.
• В C++ сумма int расширяется до long long до сложения; размер должен помещаться в int. Python int расширяется автоматически, но арифметика не постоянна для неограниченно больших чисел.

Следующий шаг

• Полный урок: поиск пары и доказательство сдвига
• Указатели в одном направлении: скользящее окно
• Задачи и самостоятельная практика