Выбор ответа Junior Два указателя спрашивают часто обновлено
Пара с суммой в отсортированном массиве
Вопрос
Массив отсортирован по возрастанию. Нужна пара с суммой target и память O(1). Какой подход?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Два указателя с концов навстречу. Отсортированность позволяет отбрасывать варианты: если сумма меньше target, левый элемент ни с кем справа не даст target, его можно пропустить.
Варианты ответа
- Map «значение → индекс» за один проход
- Перебор всех пар вложенным циклом
- Бинарный поиск пары для каждого элемента
- Два указателя с концов навстречуправильный ответ
Разбор
Отсортированность позволяет отбрасывать варианты: если сумма меньше target, левый элемент ни с кем справа не даст target, его можно пропустить. O(n) времени, O(1) памяти.
- Map тоже O(n), но тратит O(n) памяти и не использует сортировку.
- Перебор O(n²).
- Бинарный поиск для каждого элемента O(n log n), хуже двух указателей.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.