Алгоритми та структури даних · Junior · Запитання 62 з 75
Two Sum: знайти два числа в невідсортованому масиві, що в сумі дають target. Який підхід за O(n)?
- 1Відсортувати масив і повернути два найменші елементи
- 2Перебрати всі можливі пари двома вкладеними циклами
- ✓Правильна відповідь: Перевіряти, чи є
target - xу map уже бачених чисел
Пояснення
Один прохід: якщо target - x уже траплялося, пару знайдено; інакше запам'ятовуємо x і його індекс. Перебір пар - O(n²). Сортування дає O(n log n) і втрачає вихідні індекси.