Two Sum

The problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Function: def two_sum(nums, target):

Example input (a JSON list of arguments): [[2, 7, 11, 15], 9]
Expected output: [0, 1]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Store previously seen values with their indices.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target-n in seen: return [seen[target-n], i]
        seen[n] = i
    return []

Why it works

Store previously seen values with their indices. Look up the complement before inserting the current index, so one element cannot be used twice. Exactly one valid pair is assumed.

Complexity: O(n) time / O(n) space.

Time: O(n) time · Space: O(n) space