Анализ исходного кода
- Вложенные циклы пробегают все пары индексов: время работы $O(n^2)$, где $n=$ len(arr).
- Дополнительная память помимо результата — константна $O(1)$; итоговый список пар может иметь в худшем случае $\Theta (n^2)$ элементов, т.е. итоговая память $O(n^2)$.
Задача уточнения: надо ли возвращать все индексные пары (как в оригинале) или только уникальные по значению пары. Предложу оба эффективных варианта.
1) Если нужен только один экземпляр каждой пары значений (каждая комбинация $x,-x$ — один раз)
Алгоритм: проход по массиву с множеством "seen" и множеством результатов (чтобы не дублировать).
Время: $O(n)$. Память: $O(n+p)$, где $p$ — число уникальных пар (обычно $p\le n$).
Пример (псевдо-/Python):
def unique_value_pairs(arr):
seen = set()
res = set()
for x in arr:
if -x in seen:
a, b = (x, -x) if x <= -x else (-x, x)
res.add((a, b))
seen.add(x)
return list(res)
Особенность: нули добавятся как одна пара $(0,0)$ только если есть хотя бы два нуля.
2) Если нужно точно те же все индексные пары (включая дубликаты по индексам)
Алгоритм: хеш-таблица, хранящая ранее встретившиеся значения (или их индексы / счётчики). При обработке текущего элемента сразу генерируем пары с уже встреченными дополнениями — каждый индексный набор генерируется ровно один раз.
Время: $O(n+k)$, где $k$ — число возвращаемых пар (включая $k=\Theta (n^2)$ в худшем случае). Память: $O(n+k)$.
Пример:
from collections import defaultdict
def all_index_pairs(arr):
positions = defaultdict(list) # value -> list of indices (или просто counts, если не нужны индексы)
res = []
for j, x in enumerate(arr):
comp = -x
for i in positions[comp]: # генерация всех пар (i,j) с суммой 0
res.append((arr[i], arr[j]))
positions[x].append(j)
return res
Особенность: для нулей будет сгенерировано $\left(\genfrac{}{}{0ex}{}{c}{2}\right)$ пар, где $c$ — количество нулей.
Выводы по сложностям
- Исходный: время $O(n^2)$, доп. память $O(1)$ (без результата), память с результатом — до $O(n^2)$.
- Улучшенный (уникальные значения): время $O(n)$, память $O(n)$.
- Улучшенный (все индексные пары): время $O(n+k)$, память $O(n+k)$, где $k$ — число возвращаемых пар.
Выберите вариант в зависимости от требуемой семантики результата (уникальные по значению или все индексные пары).