Решить вслух: поиск пары с заданной суммой
Вопрос
Given an array of integers and a target, return the indices of two numbers that add up to the target. Talk me through how you would solve it.
Дан массив чисел и target, верните индексы двух чисел с суммой target. Расскажите, как будете решать.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Уточнил условие: дубликаты, всегда ли есть ответ, можно ли один элемент дважды
Назвал brute-force и его сложность O(n squared)
Предложил хеш-таблицу: что храним и почему
Назвал итоговую сложность по времени и памяти
Предложил прогнать пример и edge cases
Что могут спросить следом
- What if the array is sorted?
- What if there are multiple valid pairs?
- Can you do it with O(1) extra space?
Разбор
Let me make sure I understand. I get an array of integers and a target, and I need to return the indices of two different elements that sum to the target. Can I assume there's always exactly one answer? And can the array contain duplicates?
OK. The brute-force approach would be to check every pair with two nested loops, which is O(n squared) time.
We can do better with a hash map. I'll iterate over the array once, and for each number I'll check if target minus that number is already in the map. If it is, I return both indices. If not, I store the current number with its index.
That's O(n) time and O(n) space for the map. Let me trace through a quick example: two, seven, eleven, target nine. At index zero, I store two. At index one, nine minus seven is two, which is in the map, so I return zero and one.
For edge cases, I'd check an empty array and duplicates like three and three with target six.
Сложные места:
- nested loops: вложенные циклы.
- target minus that number: target минус это число.
- trace through: пройтись по шагам.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.