1

Suppose we have a list A that contains integers in it. 

A = [2,4,5,6,7]

Then given a target integer t

t = 6

I'd like to find an index tuple of two elements which makes t by summing up. 

return [0,1]

I had used my python and coded like below:

def myMethod(A,t):
    for i in range(len(A)):
        for j in range(i,len(A)):
            if A[i] + A[j] == target:
                return([i,j])

This works, but some one told me there are better method only takes O(n) complexity on average.

How could it be possible?

Any hint?

Beverlie
  • 441
  • 1
  • 6
  • 19
  • look here: https://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa – will7200 Jun 15 '18 at 03:12

1 Answers1

0

Yes, this can be done in O(n). The trick is to keep an inverted index of where each number is in the list.

Once that is done, you can traverse the list and look if the difference between your requested sum and the current element is in the list, and if so where. Since dict uses hashes for lookup, this last step is done in O(1).

def find_sum(s, lst):
    indices = {x: i for i, x in enumerate(lst)}

    for i, x in enumerate(lst):
        target = s - x
        if target in indices:
            return (i, indices[target])

    return None

lst = [2, 4, 5, 6, 7]
print(find_sum(6, lst)) # (0, 1)

This solution could be adapted to return all such pairs by making indices store sets of indices instead of a single one.

Olivier Melançon
  • 20,340
  • 3
  • 37
  • 69