Two Sum problem in Python

Two Sum is a classic interview problem: given a list of numbers and a target, find the positions of two different numbers that add up to the target.

The program

def two_sum(nums, target):
    seen = {}  # number -> its position in the list
    for i, n in enumerate(nums):
        needed = target - n
        if needed in seen:
            return seen[needed], i
        seen[n] = i
    return None


print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([3, 3], 6))
print(two_sum([-4, 10, 8, 1], 4))
print(two_sum([1, 2, 3], 100))

(0, 1)
(1, 2)
(0, 1)
(0, 2)
None

How it works

• For each number n, the partner it needs is target - n.
• seen remembers every number already passed, with its position. Checking needed in seen on a dictionary is fast, however large the dictionary is.
• If the partner was seen earlier, the answer is its position and the current position.
• The number is added to seen only after the check. That is why [3, 2, 4] with target 6 does not pair the 3 with itself. It also makes [3, 3] work: the second 3 finds the first one.
• If no pair exists, the loop ends and the function returns None.

Why not two loops?

The direct way checks every pair:

def two_sum_slow(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return i, j
    return None


print(two_sum_slow([2, 7, 11, 15], 9))

(0, 1)

It gives the same answers, but for a list of n numbers it can check about n × n / 2 pairs. For 100,000 numbers that is about 5 billion checks. The dictionary version goes through the list once.