Алгоритми та структури даних · Middle · Запитання 19 з 75
Two Sum на відсортованому масиві: який підхід за O(n) без додаткової пам'яті?
- 1Бінарний пошук пари для кожного елемента
- 2Покласти всі елементи в хеш-таблицю перед пошуком
- ✓Правильна відповідь: Два вказівники з обох кінців, які рухають залежно від суми
Пояснення
Відсортованість підказує, який вказівник рухати: збільшення лівого значення збільшує суму, зменшення правого зменшує. Хеш-таблиця теж дає O(n), але потребує O(n) пам'яті.