Время O(n), дополнительная память O(1). На каждом шаге один указатель приближается к другому, поэтому суммарно выполняется не более линейного числа сдвигов.
Сложность поиска пары двумя указателями
Время O(n), дополнительная память O(1). На каждом шаге один указатель приближается к другому, поэтому суммарно выполняется не более линейного числа сдвигов.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
В отсортированном массиве длины n ищут пару с заданной суммой: левый указатель растёт при слишком маленькой сумме, правый уменьшается при слишком большой. Оцените сложность.
Ответ
Время O(n), дополнительная память O(1). На каждом шаге один указатель приближается к другому, поэтому суммарно выполняется не более линейного числа сдвигов.
Если массив сначала нужно сортировать, добавьте стоимость сортировки и её памяти. Метод использует монотонность отсортированных значений, поэтому для произвольного порядка без подготовки он некорректен. Проверяйте left < right, чтобы не использовать один и тот же элемент дважды.