amard33p
2/1/2020 - 1:56 PM

## twosum.py

``````'''
Multiple ways to return 2 elements in a list that add up to a target value

Assumptions:
* Both inputs are valid
* Unsorted list of ints
* There is exactly one solution
* List fits in memory
'''

import timeit
from itertools import combinations

# Basic
def two_sum0(nums, target):
for i in range(len(nums)):
for j in range(len(nums)):
if (nums[i] + nums[j]) == target:
return [nums.index(nums[i]), nums.index(nums[j])]

# Using enumerate
def two_sum1(nums, target):
for idx1, i in enumerate(nums):
for idx2, j in enumerate(nums[idx1 + 1:], start = idx1 + 1):
if i + j == target:
return [idx1, idx2]

# Using itertools.combinations
def two_sum2(nums, target):
for numbers in combinations(nums, 2):
if sum(numbers) == target:
return [nums.index(number) for number in numbers]

# Sorted search
def two_sum3(nums, target):
sorted_nums = sorted(nums)
lo_index = 0
hi_index = len(sorted_nums) - 1
while lo_index < hi_index:
sum = sorted_nums[lo_index] + sorted_nums[hi_index]
if sum < target:
lo_index += 1
elif sum > target:
hi_index -= 1
else:
return [nums.index(sorted_nums[lo_index]), nums.index(sorted_nums[hi_index])]

# Fastest. Using a lookup table
def two_sum4(nums, target):
_cache = set()
for index, num in enumerate(nums):
pair = target - num
if pair in _cache:
return [nums.index(pair), index]

print(two_sum0([1, 3, 2, -7, 5], 8))
print(two_sum1([1, 3, 2, -7, 5], 8))
print(two_sum2([1, 3, 2, -7, 5], 8))
print(two_sum3([1, 3, 2, -7, 5], 8))
print(two_sum4([1, 3, 2, -7, 5], 8))

print(min(timeit.repeat('two_sum0([1, 3, 2, -7, 5], 8)', 'from __main__ import two_sum0')))
print(min(timeit.repeat('two_sum1([1, 3, 2, -7, 5], 8)', 'from __main__ import two_sum1')))
print(min(timeit.repeat('two_sum2([1, 3, 2, -7, 5], 8)', 'from __main__ import two_sum2')))
print(min(timeit.repeat('two_sum3([1, 3, 2, -7, 5], 8)', 'from __main__ import two_sum3')))
print(min(timeit.repeat('two_sum4([1, 3, 2, -7, 5], 8)', 'from __main__ import two_sum4')))
``````