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