Разбор олимпиадных задач

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

Рассмотрим задачу: "Дан отсортированный массив чисел. Найдите пару чисел, сумма которых равна заданному числу X".

Плохое решение (в лоб): запустить вложенный цикл и перебрать все пары. Сложность O(N²). При N=100 000 будет зависание (TL).

Отличное решение (Метод двух указателей): ставим один указатель в начало массива, второй в конец. Если их сумма меньше X, сдвигаем левый указатель вправо. Если больше X — сдвигаем правый влево. Сложность составит всего O(N)!