Алгоритми та структури даних · Senior · Запитання 64 з 75
Як знайти всі пари з заданою сумою в масиві з дублікатами, не рахуючи двічі?
- 1Сортувати й шукати бінарним пошуком кожен елемент, додаючи кожен збіг
- ✓Правильна відповідь: Порахувати значення в map і поєднати лічильники, врахувавши x = target - x
- 3Покласти значення в
Setі пройти його один раз
Пояснення
Для кожного різного x поєднайте його з count[target - x]; коли x дорівнює доповненню, беріть c × (c - 1) / 2. Обробляйте кожну пару значень один раз (x < доповнення). Set втрачає лічильники.