Объясни метод двух указателей
Вопрос
Объясни подход «два указателя» на задаче о паре с суммой в отсортированном массиве и его сложность.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Говорит, что опирается на отсортированность
Описывает правило сдвига: мало, левый вправо; много, правый влево
Объясняет, почему не теряем ответ: отбрасываем заведомо неподходящий элемент
Сложность O(n) времени и O(1) памяти
Сравнивает с Map: тоже O(n), но O(n) памяти
Что могут спросить следом
- А если массив не отсортирован?
- Как найти все пары без повторов?
- Как обобщить на 3Sum?
Разбор
Ставлю левый указатель на начало, правый на конец. Смотрю на сумму. Если она меньше target, левый элемент ни с кем справа не даст нужную сумму, потому что правее всё только меньше или равно текущему правому, и я двигаю левый вправо. Если сумма больше, симметрично двигаю правый влево. Если равна, нашёл. Каждый шаг отбрасывает один элемент, поэтому шагов не больше n: O(n) по времени и O(1) по памяти. Хеш-таблица дала бы такое же время, но O(n) памяти. Если массив не отсортирован, сортировка добавит O(n log n), и тогда Map выгоднее. Для 3Sum фиксирую первый элемент и внутри запускаю те же два указателя: O(n²).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.