Информатика · объяснение и практика

Когда упорядоченность позволяет двигать два указателя навстречу

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Структуры данных · Учебная карта

Главная мысль

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

Один шаг исключает несколько пар

Пусть записаны числа [−3,1,4,6,10], а нужна сумма 7. Сначала проверяем крайние: −3+10=7. Пара найдена сразу. Теперь изменим цель на 8. Сумма крайних мала, поэтому число −3 больше не понадобится: с любым другим доступным числом оно даст не больше, чем с максимальным 10.

Сдвигаем левый указатель к 1. Получается 1+10=11, это много. Число 10 тоже исключаем: с любым оставшимся левым кандидатом сумма будет не меньше 11. Следующая пара 1+6=7 мала, затем 4+6=10 велика. Указатели сходятся, поэтому разных позиций с суммой 8 нет.

Пример

Для цели 8 последовательность проверок: 7, 11, 7, 10; решения нет.

Каждый переход следует из порядка значений. Мы не отбрасываем число по догадке: заранее знаем, что все ещё не проверенные пары с ним тоже не подходят.

Индексы важнее одинаковых значений

В массиве [2,4,4,9] сумму 8 дают две разные позиции со значением 4. Такая пара допустима. В массиве [4] получить сумму 8 нельзя, если требуется два элемента, а не два использования одного элемента. Поэтому цикл продолжается только пока левый индекс строго меньше правого.

Отрицательные числа не мешают рассуждению для отсортированной суммы двух значений. Но без сортировки направление перехода не обосновано. Если ответ должен содержать исходные номера элементов, сортируют пары «значение, исходный номер», иначе найденные позиции будут относиться уже к новому порядку.

Не переносите правило на любую задачу с двумя границами

Если массив уже упорядочен, каждый указатель проходит не больше длины массива и общий поиск линейный. Если сначала нужна сортировка, её время добавляется к общей стоимости. Для одной лишь проверки существования пары можно также рассматривать множество ранее встреченных дополнений, но у него другие требования к памяти.

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

От чтения к действию

А теперь — вы

В отсортированном массиве [1,3,7,12] ищут сумму 10. Текущие указатели стоят на 1 и 12. Какой переход обоснован?

Частые вопросы

Почему при слишком большой сумме не двигают левый указатель вправо?

Это не уменьшит сумму в неубывающем массиве. Нужно уменьшать правое значение, иначе направление исключения не соответствует сравнению.

Две четвёрки считаются двумя элементами?

Да, если они хранятся на разных допустимых позициях. Равенство значений не делает позиции одним и тем же элементом.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться