Find equal pairs

Problem


Given an array A of unique integers, find the index of values that
satisfy A + B =C + D, where A,B,C & D are integers values in the
array. Find all combinations of quadruples.

I posted two versions of solutions and am wondering if there are any further smart ideas to make it run faster. I thought there might be some ideas which sort the list first, and leveraging sorting behavior, but I cannot figure out anything so far.

My code is \$O(n^2)\$ time complexity in the first version, where \$n\$ is the number of elements, and \$O(s^2)\$ in the second version, where \$s\$ is the max possible sum of elements.

from collections import defaultdict

def find_equal_pair1(numbers):
    sum_map = defaultdict(list)
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            sum_map[i+j].append((numbers[i], numbers[j]))

    result = []
    for v in sum_map.values():
        if len(v) > 1:
            result.append(v)
    return result

def find_equal_pair2(numbers):
    sum_upper_bound = max(numbers) * 2 - 1
    sum_lower_bonud = numbers[1] + numbers[2]
    numbers_set = set(numbers) # to make look-up existence O(1)
    sum_map = defaultdict(list)
    for s in range(sum_lower_bonud, sum_upper_bound + 1):
        for i in range(1, (s-1)//2 + 1):
            if i in numbers_set and s-i in numbers_set:
                sum_map[s].append((i, s-i))
    result = []
    for v in sum_map.values():
        if len(v) > 1:
            result.append(v)
    return result

if __name__ == "__main__":
    print find_equal_pair1([1,2,3,4])
    print find_equal_pair2([1,2,3,4])

Problem analysis

Since we know that each element in numbers is unique, we are guaranteed that \$s \gt n\$. So I wouldn't choose the second solution. It's even more obvious using numbers = [1, 2, 10000, 10001] where \$10002 = 10000 + 2 = 10001 + 1\$ will be found quickly by the first version but will take a long time with the second one.

Let's focus on the first version, then.

Bug

First off, you swapped storage position for the sum of 2 elements and their indexes:

sum_map[i+j].append((numbers[i], numbers[j]))

Should be:

sum_map[numbers[i]+numbers[j]].append((i, j))

Next, the exercise ask for every combination of quadruplets but you are returning a list of couples. Meaning that you will have to kind of repeat the logic to perform combinations.

Combinations

Whenever you need unique combinations of \$n\$ elements from an iterable, instead of using \$n\$ for loops on indexes, use itertools.combinations. It is both cleaner and faster (since it is implemented in C). It also easily handle cases where the iterable length is less than \$n\$.

Here you also need the indexes, so I suggest the following rewrite using enumerate:

from collections import defaultdict
from itertools import combinations

def find_equal_pair(numbers):
    sum_map = defaultdict(list)
    for (index1, element1), (index2, element2) in combinations(enumerate(numbers), 2):
        sum_map[element1+element2].append((index1, index2))

    result = []
    for v in sum_map.values():
        for (a, b), (c, d) in combinations(v, 2):
            result.append((a, b, c, d))
    return result

You can also turn the results formatting into a listcomprehension:

return [
        (a, b, c, d)
        for values in sum_map.values()
        for (a, b), (c, d) in combinations(values, 2)
    ]

StackExchange Code Review Q#152219, answer score: 4