Кратко — два стандартных пути: хеш-таблица для среднего случая $O(n)$ и сортировка + два указателя для детерминированного $O(n\log n)$. Ниже — как именно, какие структуры и как учесть дубликаты и память.
1) Хеш-таблица (среднее время $O(n)$, память $O(u)$, где $u$ — число различных значений)
- Структура: словарь value -> count (если нужно только количество пар по значениям) или value -> список индексов (если нужны конкретные индексы).
- Алгоритм (подсчёт количества пар по значениям):
- Проход: для каждого значения $x$ увеличивать $freq[x]$.
- Потом для каждого уникального $x$ считать комплемент $y=S-x$.
- Если $x<y$: добавить $freq[x]\times freq[y]$.
- Если $x=y$: добавить $\left(\genfrac{}{}{0ex}{}{freq[x]}{2}\right)=\frac{freq[x](freq[x]-1)}{2}$.
- Либо во время одного прохода: для текущего $x$ добавлять к ответу $freq[S-x]$ и затем увеличивать $freq[x]$\; это даёт тот же результат без двойного прохода.
- Память: хранится $freq$ — $O(u)$. Если хранить индексы для вывода всех пар, память может вырасти до $O(n)$ и число пар в выводе — до $O(n^2)$.
- Замечание: unordered_map даёт амортизированное $O(1)$ для вставки/поиска (итог $O(n)$), но в худшем случае может быть хуже; для детерминированного поведения используйте сбалансированное дерево (map) — тогда время $O(n\log u)$.
2) Сортировка + два указателя (детерминированно $O(n\log n)$ времени, дополнительная память $O(1)$ если сортировать in-place)
- Структура: массив отсортированных значений (или пар (value,index), если нужны индексы).
- Алгоритм:
- Отсортировать массив — $O(n\log n)$.
- Поставить указатели $l=0$, $r=n-1$.
- Пока $l<r$:
- Если $a[l]+a[r]<S$: $l++$.
- Если $a[l]+a[r]>S$: $r--$.
- Если $a[l]+a[r]=S$: посчитать повторения одинаковых значений:
- Пусть $x=a[l]$, $y=a[r]$.
- Если $x\ne y$: считать $cntL$ — число равных $x$ подряд слева, $cntR$ — число равных $y$ подряд справа, добавить $cntL\times cntR$, затем $l+=cntL,r-=cntR$.
- Если $x=y$: осталось $m=r-l+1$ одинаковых элементов, добавить $\left(\genfrac{}{}{0ex}{}{m}{2}\right)=\frac{m(m-1)}{2}$ и закончить.
- Память: только массив (если можно сортировать на месте) — дополнительная $O(1)$ или $O(\log n)$ для рекурсивной сортировки; если требуется сохранить исходные индексы, храните пары — дополнительная память $O(n)$.
3) Вывод конкретных пар (индексы) vs только подсчёт
- Подсчёт по значениям: достаточно частот $freq$ — память $O(u)$.
- Перечисление всех пар индексов: если число пар велико, это по определению займёт много времени/памяти (вывод размер $k$). Хранение value->список индексов даёт память $O(n)$; при большом количестве пар лучше стримить (генерировать пары по мере вычисления) или использовать внешнее хранение.
4) Ограничения по памяти / большие данные
- Если массив не помещается в ОП:
- Внешняя сортировка (external sort) + два указателя по файлу — детерминированно, требует диска.
- Хеш‑разбиение на бакеты по значению: записать элементы в $B$ файлов по хешу, затем для каждого бакета и его «комплементарного» бакета (хеш(S - x)) загружать пары в память и обрабатывать. Нужно гарантировать, что каждая пара попадёт в обрабатываемые комбинации бакетов.
- Если нужен только приближённый счёт — использовать скетчи (Count‑Min) — даёт приближение, но не точный результат.
- Если число уникальных значений невелико, выгоднее хранить только частоты.
5) Практические советы и подводные камни
- Если элементы — большие целые, проверяйте переполнение при суммах.
- Для вещественных чисел сравнения на равенство проблематичны — используйте эпсилон.
- Если нужен гарантированный $O(n)$ во всех случаях (а не амортизированный), не полагайтесь на небезопасные хеш‑таблицы — используйте алгоритмы на сортировке ($O(n\log n)$) или защищённые хеш‑реализации.
- Помните: если выходной размер $k$ велик (например $k=\Theta (n^2)$), время/память не могут быть меньше $O(k)$.
Краткая сводка:
- Получить среднее время $O(n)$: использовать хеш-таблицу (value->count или value->list).
- Получить детерминированное $O(n\log n)$: отсортировать и сделать два указателя (умеет эффективно обрабатывать дубликаты).
- Для больших данных: внешняя сортировка или хеш‑разбиение; аккуратно работать с памятью и учесть размер вывода.
Если нужно, могу привести компактный пример кода (Python) для подсчёта количества пар либо для перечисления индексов.