Объясни Two Sum через хеш
Вопрос
Объясни подход к задаче «найти два числа с суммой target» и его сложность.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Сначала называет перебор O(n²) как базовое решение
Идея: для x ищем дополнение target - x в Map
Проверяет Map до вставки x, чтобы не взять один элемент дважды
Сложность O(n) времени и O(n) памяти
Упоминает краевые случаи: дубликаты, нет ответа
Что могут спросить следом
- Что если массив отсортирован?
- Что если нужно вернуть все пары без повторов?
- Как быть, если память ограничена?
Разбор
Базовое решение: перебрать все пары, это O(n²). Его можно улучшить, если заметить, что для каждого x нам нужен конкретный партнёр: target - x. Значит, нужен быстрый поиск по значению, это Map «значение → индекс». Иду по массиву один раз: для текущего x смотрю, есть ли в Map target - x; если есть, возвращаю пару индексов; если нет, кладу x. Проверка до вставки важна: так элемент не сложится сам с собой, а пара из двух одинаковых значений вроде [3, 3] при target 6 найдётся. Время O(n), память O(n). Если массив уже отсортирован, хватит двух указателей с O(1) памяти.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.