Сглаживание вложенных циклов / уменьшение сложности - алгоритм подсчета дополнительных пар

Недавно я пытался решить некоторую задачу на Python и нашел решение, которое, кажется, имеет сложность O (n log n) , но я считаю, что это очень неэффективно для некоторых входных данных ( например, первый параметр представляет собой 0 и пары представляют собой очень длинный список нулей).

Он также имеет три уровня для петель. Я считаю, что его можно оптимизировать, но на данный момент я не могу оптимизировать его, я, вероятно, просто упускаю что-то очевидное;)

Итак, в основном проблема заключается в следующем:

Данный список целых чисел ( values ​​), функция должна возвращать количество пар индексов, которые соответствуют следующим критериям:

• позволяет предположить, что одна индексная пара представляет собой кортеж, например (index1, index2) ,
• тогда значения [index1] == complementary_diff - values ​​[index2] истинно,

Пример : Если задан список вида [1, 3, -4, 0, -3, 5] как значения и 1 как complementary_diff , функция должна вернуть 4 (что является длиной следующего списка пар индексов: [(0, 3), (2, 5), (3, 0), (5 , 2)] ).

Это то, что у меня есть до сих пор, большую часть времени он должен работать идеально, но, как я уже сказал, в некоторых случаях он мог работать очень медленно, несмотря на приблизительную сложность O (n log n) (похоже, пессимистическая сложность равна O (n ^ 2) ).

def complementary_pairs_number (complementary_diff, values):
    value_key = {} # dictionary storing indexes indexed by values
    for index, item in enumerate(values):
        try:
            value_key[item].append(index)
        except (KeyError,): # the item has not been found in value_key's keys
            value_key[item] = [index]
    key_pairs = set() # key pairs are unique by nature
    for pos_value in value_key: # iterate through keys of value_key dictionary
        sym_value = complementary_diff - pos_value
        if sym_value in value_key: # checks if the symmetric value has been found
            for i1 in value_key[pos_value]: # iterate through pos_values' indexes
                for i2 in value_key[sym_value]: # as above, through sym_values
                    # add indexes' pairs or ignore if already added to the set
                    key_pairs.add((i1, i2))
                    key_pairs.add((i2, i1))
    return len(key_pairs)

Для данного примера это ведет себя так:

>>> complementary_pairs_number(1, [1, 3, -4, 0, -3, 5])
4

Если вы видите, как код можно «упростить» или «упростить», дайте мне знать.

Я не уверен, что просто проверка на complementary_diff == 0 и т. Д. Является лучшим подходом - если вы так думаете, дайте мне знать.

РЕДАКТИРОВАТЬ: Я исправил пример (спасибо, unutbu!).