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))
