Розбір для Пари з заданою сумою
Памʼятайте, що цей розбір слід використовувати лише коли ви застрягли, і не копіювати код з нього. Будь ласка, поважайте автора задачі та автора розбору.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Розбір розв'язку
Наївний підхід за ~O(n^2)~ (перебір усіх пар) не встигає за обмежений час при ~n \le 2 \cdot 10^5~.
Ефективний розв'язок — ~O(n \log n)~:
- Відсортувати масив.
- Використати два вказівники (
two pointers): один починається з початку, інший — з кінця. Якщо сума менша за ~k~ — рухаємо лівий вказівник праворуч, якщо більша — рухаємо правий вказівник ліворуч. Якщо сума дорівнює ~k~ — потрібно акуратно порахувати кількість пар для однакових значень (за допомогою підрахунку кількості однакових елементів зліва і справа), щоб уникнути подвійного підрахунку чи пропуску пар.
Альтернативно можна скористатися хеш-таблицею (unordered_map) для підрахунку кількості елементів з потрібним доповненням до ~k~, проходячи масив зліва направо і додаючи в таблицю вже оброблені елементи.
Коментарі