Выбор ответа Middle Два указателя обновлено
3Sum: сложность
Вопрос
Какая лучшая известная на собесе сложность для «найти все уникальные тройки с суммой 0»?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n²): сортировка и два указателя. Сортируем (O(n log n)), фиксируем первый элемент и ищем пару двумя указателями за O(n).
Варианты ответа
- O(n): Set уже виденных чисел
- O(n log n): сортировка и бинпоиск
- O(n³): перебор троек обязателен
- O(n²): сортировка и два указателяправильный ответ
Разбор
Сортируем (O(n log n)), фиксируем первый элемент и ищем пару двумя указателями за O(n). Итого O(n²). Дубликаты пропускаем сдвигом, пока значения равны.
- O(n) и O(n log n): для этой задачи на собесе такие решения не ожидаются, стандартный ответ O(n²).
- O(n³) это перебор троек.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.