Пара с заданной суммой:
перебор и указатели

Категория

Алгоритм

Уровень

Начальный

Опирается на

Глава 8.3: условие задачи 1 после уточнений

Зачем это знать

Типичная первая задача алгоритмической секции

§1Условие задачи 1

Условие уточнено в главе 8.3, здесь оно записано в окончательном виде. Во всех примерах главы используется один каталог из шести цен, чтобы сравнивать способы на одних данных.

§2Решение перебором

Самое прямое решение — проверить все пары. Внешний цикл выбирает первый товар i, внутренний — второй j. Причём j начинается с i + 1: так товар не складывается сам с собой, и каждая пара проверяется один раз. На собеседовании такое решение называют brute force, «решение в лоб», и предлагают первым — оно точно верное, и с ним сравнивают быстрое решение.

def pair_sum_brute(prices, target):
    n = len(prices)
    for i in range(n):
        for j in range(i + 1, n):
            if prices[i] + prices[j] == target:
                return (i, j)
    return None

>>> list(range(2, 5))
[2, 3, 4]
>>> for i in range(3):
...     for j in range(i + 1, 3):
...         print(i, j)
...
0 1
0 2
1 2

>>> def find():
...     return (2, 3)
...
>>> r = find()
>>> r
(2, 3)
>>> r[0]
2
>>> def nothing():
...     return None
...
>>> print(nothing())
None
>>> nothing() is None
True

Прогон ниже сделан на четырёх ценах, чтобы все проверки поместились на экран. Нажимайте «шаг →» или стрелку вправо на клавиатуре, когда блок выделен. Строка кода, которая выполнится следующей, подсвечена; справа — значения переменных и указатели i, j под ячейками списка.

Пара нашлась на шестой проверке — последней из возможных. Это худший случай перебора: каждая пара проверена ровно один раз.

§3Сколько пар в списке

У первого товара n − 1 соседей справа, у второго n − 2 и так далее до последнего, у которого соседей справа нет. Сумма (n − 1) + (n − 2) + … + 1 равна n·(n − 1) / 2. Когда пары нет, перебор проверяет их все.

Поэтому время перебора оценивается как O(n²): при увеличении списка вдвое проверок становится примерно вчетверо больше. Для масштаба: на 16 000 ценах перебор работает около 2,8 секунды на ноутбуке автора.

§4Идея указателей навстречу

Перебор не пользуется тем, что цены отсортированы. А по порядку сразу видно, какие пары проверять бесполезно. Поставим указатель i на самую дешёвую цену, j — на самую дорогую и посмотрим на их сумму.

1. Сумма равна цели. Пара найдена, возвращаем (i, j).
2. Сумма меньше цели. Сумму нужно увеличить. Правая цена уже самая большая из оставшихся, поэтому увеличить сумму может только более дорогая левая цена. Сдвигаем i вправо.
3. Сумма больше цели. Сумму нужно уменьшить. Левая цена уже самая маленькая из оставшихся, поэтому уменьшить сумму может только более дешёвая правая цена. Сдвигаем j влево.
4. Указатели встретились. Непроверенных пар не осталось, ответ None.

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

§5Поиск пары вручную

Прежде чем смотреть, как это делает код, пройдите алгоритм сами. Кнопки двигают указатели; ход, который противоречит правилу, не выполняется, и под кнопками появляется объяснение, какую пару он бы потерял. В наборе пять примеров, среди них два без ответа — там закончить нужно кнопкой «Пары нет», когда указатели встретятся.

В последнем примере, [100, 250, 600] с целью 500, указатели сходятся на цене 250. Сумма 250 + 250 как раз равна 500, но это один и тот же товар, поэтому пары нет. Отсюда правило остановки: поиск идёт, пока между указателями есть хотя бы два товара, то есть пока i < j.

§6Сборка функции из строк

Правило из §4 записывается функцией из одиннадцати строк. Строки перемешаны, отступы у них сохранены. Расставьте их по порядку стрелками или перетаскиванием и нажмите «Проверить порядок». Готовая функция появится ниже, в пошаговом прогоне §7.

Два места стоит разобрать отдельно. Проверка s == target стоит раньше сдвига: если найденную пару не вернуть сразу, один из указателей сдвинется, и функция вернёт уже другие индексы. А return None стоит после цикла, на уровне while: внутри цикла он завершил бы функцию на первом же шаге.

>>> prices = [300, 450, 700]
>>> i, j = 0, len(prices) - 1
>>> i, j
(0, 2)
>>> prices[j]
700

>>> i = 0
>>> while i < 3:
...     i += 1
...
>>> i
3

Напишите функцию сами в окне ниже, прямо на странице. «Запустить тесты» проверяет код на семи входах; часть из них заготовка проходит сразу: там, где верный ответ — None. Строка «Свой вызов» выполняет любой код с вашей функцией и печатает результат. Первый запуск загружает Python в браузер, около 10 МБ.

§7Пошаговый прогон кода

Собранная функция на двух входах. Бледные ячейки — цены, которые уже исключены. Подписи под кодом объясняют каждый ход тем же правилом, что в §4. Вкладки переключают два входа: в первом пара есть, во втором нет.

§8Сколько шагов делают указатели

Каждый ход сдвигает i вправо или j влево на одну позицию, и назад указатели не возвращаются. В начале между ними n − 1 позиция, цикл заканчивается, когда расстояние становится нулевым. Значит, ходов не больше n − 1, а время — O(n). Дополнительная память — три переменные i, j, s, то есть O(1).

Ползунок меняет длину списка. Полосы показывают число проверок в худшем случае, когда пары нет, а время рассчитано по замеру на Python 3.12.

§9Проверьте себя