Сортировка и два указателя

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

Зачем сортировать массив

Пусть дан массив чисел и требуется найти два элемента с заданным свойством: сумма равна \(S\), разность не превышает \(D\), произведение меньше порога или оба элемента лежат в одном диапазоне. Если проверять все пары, получится \(O(n^2)\) сравнений. После сортировки элементы расположены по возрастанию, поэтому порядок становится дополнительной информацией.

Для задач на пары чаще всего нужна сортировка по возрастанию. Она позволяет сравнить сумму крайних элементов с целью и понять, какой указатель нужно сдвинуть. Обычно сортировка занимает \(O(n\log n)\), а последующий проход — \(O(n)\).

Два указателя для поиска пары

Для поиска пары с суммой \(S\) поставим левый указатель \(L\) в начало массива, а правый \(R\) — в конец. Рассмотрим сумму \(a_L+a_R\). Если она меньше \(S\), нужно увеличить сумму: самый безопасный шаг — увеличить \(L\). Если сумма больше \(S\), уменьшаем её, сдвигая \(R\) влево. Если сумма равна \(S\), пара найдена.

sort(a)
L = 0
R = n - 1
while L < R:
    s = a[L] + a[R]
    if s == S:
        вывести a[L], a[R]
        L = L + 1
        R = R - 1
    elif s < S:
        L = L + 1
    else:
        R = R - 1

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

Разобранный пример: количество пар с ограничением

Задача: дан отсортированный массив \([1,2,3,5,6,8,10]\). Сколько пар \((i,j)\), где \(i<j\), имеют сумму не больше \(10\)? Здесь не требуется перечислять только одну пару: нужно учесть все подходящие пары.

Всего получили \(5+4+2=11\) пар. Важен не сам набор чисел, а переход: при каждом увеличении \(L\) правый указатель не возвращается вправо. Поэтому после сортировки подсчёт выполняется за \(O(n)\).

def count_pairs_at_most(a, limit):
    a.sort()
    left, right = 0, len(a) - 1
    answer = 0
    while left < right:
        if a[left] + a[right] <= limit:
            answer += right - left
            left += 1
        else:
            right -= 1
    return answer

Диапазоны и непрерывные группы

После сортировки удобно искать максимальный диапазон, в котором разность между крайним и первым элементом не превышает \(D\). Левый указатель обозначает начало текущего диапазона, правый — его конец. Пока \(a_R-a_L\le D\), расширяем диапазон вправо. Если условие нарушилось, двигаем \(L\) вправо, пока оно снова не станет верным.

Так находят максимальное число элементов, укладывающихся в отрезок длины \(D\), число пар с разностью не больше \(D\), а также группы элементов, близких по значению. Если требуется обработать все одинаковые значения как одну группу, применяют приём обработки групп одинаковых элементов: указатель пропускает весь блок равных элементов.

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

Типовые схемы и границы

• Пара с точной суммой: при сравнении суммы с целью двигаем один из указателей; при совпадении фиксируем ответ.
• Пара с суммой не больше цели: если крайняя пара подходит, добавляем сразу \(R-L\) пар и увеличиваем \(L\).
• Максимальный диапазон: увеличиваем \(R\), а при нарушении условия сдвигаем \(L\) до восстановления условия.
• Группы одинаковых элементов: находим левую границу группы, затем пропускаем все равные значения.
• Тройка элементов: внешний цикл фиксирует первый элемент, а для оставшихся используется поиск пары; это связано со страницей поиск тройки элементов.

Оценка сложности и подготовка ответа

Сортировка требует памяти и времени в зависимости от используемого алгоритма, но в экзаменационных решениях обычно достаточно указать \(O(n\log n)\). Два указателя делают не более \(n\) шагов каждым, поэтому их часть имеет сложность \(O(n)\). При ручном решении полезно выписать таблицу с \(L\), \(R\), значениями \(a_L\), \(a_R\) и результатом проверки.