Метод двух указателей
Метод двух указателей: пары с заданной суммой и скользящее окно за O(n).
Идея метода: два индекса ходят по массиву только вперёд (или навстречу друг другу) и никогда не возвращаются. Каждый указатель сдвигается не больше n раз — итого O(n) вместо O(n²) перебора всех пар.
Классика номер один: в ОТСОРТИРОВАННОМ массиве найти пару с суммой X. Ставим указатели на края: если сумма мала — двигаем левый вправо (сумма вырастет), если велика — правый влево.
Пара с суммой X. Введите: 5 12, затем отсортированный массив 1 3 5 7 9
Почему это верно: если a[l] + a[r] < X, то a[l] в паре с ЛЮБЫМ элементом левее r даст ещё меньше — значит, a[l] можно смело исключить. Симметрично для правого. Ни одна возможная пара не теряется.
Классика номер два — скользящее окно: оба указателя идут в одну сторону. Найдём самый длинный отрезок, сумма которого не превышает S: правый край расширяет окно, левый поджимается, когда сумма превысила лимит.
Самый длинный отрезок с суммой не больше S. Введите: 6 8, затем 2 4 1 3 5 2
Обратите внимание: внутренний while не делает алгоритм квадратичным — левый указатель за всю работу программы сдвинется суммарно не больше n раз.
Проверка палиндрома, которую вы писали в курсе языка, — тоже два указателя, идущие навстречу. Решите прикреплённую задачу «Проверка палиндрома», осознав её теперь как частный случай метода, и отметьте урок пройденным.