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>Yes it can be done in a way with complexity less than O(n^2). The algo is:</p>

<ol>
<li>Create a duplicate array suppose indexArr[] storing the index of the element of the original array say origArr[].</li>
<li>Sort the origArr[] in ascending order using some algo having complexity O(nLogn). Likewise also shuffle the indexArr[] while sorting the origArr[].</li>
<li>Now you have to find the pairs in the sorted array, you will run 2 loops finding all the possible combinations. Suppose you select <code>origArr[i] + origArr[i + 1] = sum.</code> </li>
<li>Now you will search iff <code>sum &lt;= origArr[n]</code> where n is the last element of the array which is the maximum element. Also if <code>sum &gt; origArr[n]</code> then you will break the inner loop as well as the outer loop as no other combinations are possible.</li>
<li>Also you will break the inner loop if <code>sum &gt; origArr[j]</code> as no other combinations are possible for that sum.</li>
</ol>

<p>PS - The worst case scenario will be O(n^2).</p>

python algorithm python-2.7