Задача с собеседования в Тинькофф.

Умеете ли решать следующую задачу?
Дается массив целых чисел 'a', найти два индекса 0 <=l<r<n, что a[l] + a[r] == target.
Думаю многие знают эту задачу, называется Two Sum. Эта задача очень часто встречалась в Яндексе.

Так вот люди в Тинькофф поменяли эту задачу:
Дается отсортированный массив целых чисел 'a', найти два индекса 0 <=l<r<n, что a[l] + a[r] == target.
Решить нужно за O(n) и без дополнительной памяти.

Решение:
-Сначала вспомним как решать с доп памятью:
Заведем хеш-таблицу has. Пройдемся циклом по массиву 'a'. Пусть мы на позиции i, нам хотелось бы найти такой j, что j < i и a[i] + a[j] == target. Мы могли бы в хеш-таблице узнать встречали ли число a[j], равным target-a[i].

Заметим, что мы вообще не использовали факт отсортированности массива.
Пусть j=0, найдем максимальный i, что a[j] + a[i] <= target. В таком случае для j=0, лучшая пара это i. Если a[i] + a[j] = target, то супер мы нашли ответ.

Пусть j=1, найдем максимальный i, что a[j] + a[i] <= target. Как думаешь i, для j=1 может быть больше чем i для j=0?
Конечно нет, а это означает мы можем применить метод двух указателей.

j будет всегда идти слева направо, а i справа налево. Как только находим сумму равная target выходим из цикла. Этот метод сработал число из за отсортированности массива.

Для практики вы можете взять задачу Two Sum из литкода, отсортировать массив который вам дают и применить метод двух указателей.

Код в комментариях.