Поиск пары элементов

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

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

При таком подходе число проверок равно \(\frac{n(n-1)}{2}\), поэтому временная сложность составляет \(O(n^2)\), а дополнительная память — \(O(1)\). Если массив отсортирован или допускается хранить уже встреченные значения, поиск иногда можно ускорить до \(O(n)\) или \(O(n\log n)\). Такой приём связан с методом двух указателей.

for i от 0 до n - 2:
    for j от i + 1 до n - 1:
        if условие(a[i], a[j]):
            обработать пару i, j