find the index of values that satisfy A + B =C + D
<p>Working on below problem, using Python 2.7. Post my code and wondering if 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 cannot figure out so far. My code is <code>O(n^2)</code> time complexity.</p>

<p><strong>Problem</strong>,</p>

<p>Given an array A of integers, find the index of values that satisfy A + B =C + D, where A,B,C &amp; D are integers values in the array. Find all combinations of quadruples.</p>

<p><strong>Code</strong>,</p>

<pre><code>from collections import defaultdict

sumIndex = defaultdict(list)

def buildIndex(numbers):
    for i in range(len(numbers)):
        for j in range(i+1,len(numbers)):
            sumIndex[numbers[i]+numbers[j]].append((i,j))

def checkResult():
    for k,v in sumIndex.items():
        if len(v) &gt; 1:
            for i in v:
                print k, i

if __name__ == "__main__":
    buildIndex([1,2,3,4])
    checkResult()
</code></pre>

<p><strong>Output</strong>, which is sum value, and indexes which sum could result in such value,</p>

<pre><code>5 (0,3)
5 (1,2)
</code></pre>

<p>faster, more Pythonic approach using <code>itertools.combinations:</code></p>

<pre><code>from collections import defaultdict
from itertools import combinations

def get_combos(l):
    d = defaultdict(list)
    for indices in combinations(range(len(l)),2):
        d[(l[indices[0]] + l[indices[1]])].append(indices)
    return {k:v for k,v in d.items() if len(v) &gt; 1}
</code></pre>

<p><hr>
<em>timing results</em></p>

<pre><code>                                             OP       this
len(l)=4, min(repeat=100, number=10000) | 0.09334  | 0.08050
len(l)=50, min(repeat=10, number=100)   | 0.08689  | 0.08996
len(l)=500, min(repeat=10, number=10)   | 0.64974  | 0.59553
len(l)=1000, min(repeat=3, number=3)    | 1.01559  | 0.83494
len(l)=5000, min(repeat=3, number=1)    | 10.26168 | 8.92959
</code></pre>

<hr>

<p><em>timing code</em></p>

<pre><code>from collections import defaultdict
from itertools import combinations
from random import randint
from timeit import repeat


def lin_get_combos(l):
    sumIndex = defaultdict(list)
    for i in range(len(l)):
        for j in range(i+1,len(l)):
            sumIndex[l[i]+l[j]].append((i,j))
    return {k:v for k,v in sumIndex.items() if len(v) &gt; 1}

def craig_get_combos(l):
    d = defaultdict(list)
    for indices in combinations(range(len(l)),2):
        d[(l[indices[0]] + l[indices[1]])].append(indices)
    return {k:v for k,v in d.items() if len(v) &gt; 1}

l = []
for _ in range(4):
    l.append(randint(0,1000))
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=100, number=10000))
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 100, number=10000))
print '%0.5f, %0.5f' % (t1, t2)

l = []
for _ in range(50):
    l.append(randint(0,1000))
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=10, number=100))
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 10, number=100))
print '%0.5f, %0.5f' % (t1, t2)

l = []
for _ in range(500):
    l.append(randint(0,1000))
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=10, number=10))
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 10, number=10))
print '%0.5f, %0.5f' % (t1, t2)

l = []
for _ in range(1000):
    l.append(randint(0,1000))
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=3, number=3))
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 3, number=3))
print '%0.5f, %0.5f' % (t1, t2)

l = []
for _ in range(5000):
    l.append(randint(0,1000))
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=3, number=1))
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 3, number=1))
print '%0.5f, %0.5f' % (t1, t2)
</code></pre>

python algorithm python-2.7