Given there's a list of random number and the amount I want to find.

For example:

[80, 98, 83, 92, 1, 38, 37, 54, 58, 89]

And I want two numbers that add up to a given total in this case it's 181. So, it's going to be (92+89). The list could be really big.

Here's the solution I come up with. But it's kinds brute force and I was wondering if there's a better way of doing this.

for i, item in enumerate(numbers):

    for j in range(i+1, len(numbers)):

        total_of_two_items = numbers[i] + numbers[j]

        if(total_of_two_items == total_number):

            print '{first_item} {second_item}'.format(first_item=i+1, second_item=j+1)

            print 'n'

Here is an alternative approach using set logic, which is O(n) in the average case:

n = 181

n2 = n//2

numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]

goodnums = {n-x for x in numbers if x<=n2} & {x for x in numbers if x>n2}

pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and (n2, n2) in pairs and numbers.count(n2) == 1:

   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

We first sort the list and then keep comparing the ends of the sorted list to get those pairs of numbers which sum to a given number. Merge sort has been used here, however any other sorting algorithm can also be used. The main logic is in the find_pairs function.

def mergeSort(A):



    if len(A) > 1:

        mid = len(A)//2

        lefthalf = A[:mid]

        righthalf = A[mid:]



        mergeSort(lefthalf)

        mergeSort(righthalf)



        # Merge the halves

        i,j,k=0,0,0



        while i<len(lefthalf) and j<len(righthalf):

            if lefthalf[i] < righthalf[j]:

                A[k] = lefthalf[i]

                i = i + 1

            else:

                A[k] = righthalf[j]

                j = j + 1

            k = k + 1



        while i < len(lefthalf):

            A[k] = lefthalf[i]

            k = k +1

            i = i + 1



        while j < len(righthalf):

            A[k] = righthalf[j]

            k = k + 1

            j = j + 1





def find_pairs(alist, item):

    # We take two flags left and right to point to the ends of the sorted list

    left = 0

    right = len(alist) - 1

    pairs = 

    while(left<right):

        # We find the sum of the numbers in at these two points.

        # If the sum is equal to our number for which we are finding pairs, we consider this pair and add it to our results

        # If the sum is greater than expected then we move the right pointer one step back to a smaller number and then compute sum again

        # If the sum is smaller than expected then we move the left pointer a step ahead and check the sum with a greater number

        sum = alist[left] + alist[right]

        if sum == item:

            pairs += [(alist[left],alist[right])]

            # Move the pointers to next elements in the list and find more pairs

            right -= 1

            left += 1

        elif sum > item:

            right -= 1

        else:

            left += 1

    return pairs





l1 = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]

mergeSort(l1)

print l1

print find_pairs(l1,181)



l2 = [-5,-2, -23, 34,21,90,1,0,65,8,-10]

mergeSort(l2)

print l2 

print find_pairs(l2,-2)

The output of the above program is:

[1, 37, 38, 54, 58, 80, 83, 89, 92, 98]

[(83, 98), (89, 92)]





[-23, -10, -5, -2, 0, 1, 8, 21, 34, 65, 90]

[(-23, 21), (-10, 8), (-2, 0)]

I came up with the following, which ends up using a dictionary as a helper to avoid the set operations and extra testing:

def sum_of_pairs_matches(K, arr):

    uniques = {i: True for i in arr}

    pairs = set()

    for val in arr:

        k = -val + K if val<K else -K - val

        if(uniques.get(k, False)):

            pairs.add(tuple(sorted([k,val])))

    return pairs

Running:

sum_of_pairs_matches(5, [-5, -4, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

will yield

{(-5, 10), (-4, 9), (-1, 6), (0, 5), (1, 4), (2, 3)}

It's really worth writing this as a function. That will make it easier to test, and it's an opportunity to give it a sensible name and a docstring describing what it does (it's not obvious from your description that you wanted to output the positions of the found numbers, rather than the numbers themselves):

def find_2sum(target, numbers):

    """Find indexes of pairs from NUMBERS that add to TARGET"""

    for i, item in enumerate(numbers):

        for j in range(i+1, len(numbers)):

            total_of_two_items = numbers[i] + numbers[j]

            if(total_of_two_items == target):

                print('{first_item} {second_item}'.format(first_item=i+1, second_item=j+1))

                print('n')



if __name__ == '__main__':

    find_2sum(181, [80, 98, 83, 92, 1, 38, 37, 54, 58, 89])

We can improve the interface by returning the index pairs instead of printing them. That pares the function down to its essential responsibility, instead of it finding and printing the results:

def find_2sum(target, numbers):

    """Find indexes of pairs from NUMBERS that add to TARGET"""

    for i, item in enumerate(numbers):

        for j in range(i+1, len(numbers)):

            if numbers[i] + numbers[j] == target:

                yield [i, j]



if __name__ == '__main__':

    for i,j in find_2sum(181, [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]):

        print('{} {}'.format(i+1, j+1))

Now, let's look at the implementation. The first thing that strikes me is that we enumerate numbers, but never use the item we obtain. We might as well have written

for i in range(len(numbers)):

Perhaps we could enumerate() the list once, and use it for both augends:

def find_2sum(target, numbers):

    """Find indexes of pairs from NUMBERS that add to TARGET"""

    numbers = list(enumerate(numbers))

    while numbers:

        i, first = numbers.pop(0)

        for j, second in numbers:

            if first + second == target:

                yield [i, j]

We still have an efficiency problem, in that we're adding every possible pair and testing it against the target sum. We can avoid the addition by using a single subtraction outside the loop, but this still requires looking at all pairs, so still scales as O(n²):

def find_2sum(target, numbers):

    """Find indexes of pairs from NUMBERS that add to TARGET"""

    numbers = list(enumerate(numbers))

    while numbers:

        i, first = numbers.pop(0)

        difference = target - first

        for j, second in numbers:

            if second == difference:

                yield [i, j]

What we really need to do now is to improve our search for difference. We'll need to use an additional data structure that can locate it in sub-linear time. The obvious choice would be a dict that maps from value to index; for a general solution, we'll need it to map to a list of indexes, because any number may appear multiple times. We can build such a map quite easily:

    index_map = collections.defaultdict(list)

    for i, item in enumerate(numbers):

        index_map[item].append(i)

The reading is a bit more involved: once we find two values that sum to the target, we need to form all combinations of the first value's indexes and the second value's indexes, like this:

    for first, indices in index_map.items():

        difference = target - first

        other_indices = index_map.get(difference, )

        for i in indices:

            for j in other_indices:

                yield [i, j]

If we do this, we'll see that we produce every pair twice, once in each order. We can fix this by ignoring the cases where the first is bigger than the second:

    for first, indices in index_map.items():

        difference = target - first

        if first < difference:

            other_indices = index_map.get(difference, )

            for i in indices:

                for j in other_indices:

                    yield [i, j]

There's another case we missed, and we can demonstrate with a simple test case:

for i,j in find_2sum((6, [2, 2, 3, 3, 3, 4, 4]):

    print('{} {}'.format(i+1, j+1))

Because 3 is exactly half of 6, we need to enumerate all the combinations of these:

        if first == difference:

            while indices:

                i = indices.pop()

                for j in indices:

                    yield [i, j]

We produce results in somewhat arbitrary order, as we're using an unsorted dict. If we want a consistent order to the results, the best way is to sort them after they are generated:

for i,j in sorted(sorted(x) for x in find_2sum(6, [2, 2, 3, 3, 3, 4, 4])):

    print('{} {}'.format(i+1, j+1))

Full program

import collections



def find_2sum(target, numbers):

    """Find indexes of pairs from NUMBERS that add to TARGET"""

    index_map = collections.defaultdict(list)

    for i, item in enumerate(numbers):

        index_map[item].append(i)



    # now read from index_map

    for first, indices in index_map.items():

        difference = target - first

        if first == difference:

            # return all distinct pairs from indices (we won't need it again)

            while indices:

                i = indices.pop()

                for j in indices:

                    yield [i, j]

        elif first < difference:

            # normal case - return all combinations of first and second

            other_indices = index_map.get(difference, )

            for i in indices:

                for j in other_indices:

                    yield [i, j]



if __name__ == '__main__':

    for i,j in find_2sum(181, [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]):

        print('{} {}'.format(i+1, j+1))



    print()

    for i,j in sorted(sorted(x) for x in find_2sum(6, [2, 2, 3, 3, 3, 4, 4])):

        print('{} {}'.format(i+1, j+1))