Two Sum

L3 Easy Arrays & Hashing

Concept

A Dictionary maps keys to values with ~O(1) lookup. As you walk the array, you can ask the dictionary whether the number you still need has already been seen.

You are given an array of integers nums and a target. Two distinct numbers in nums add up to target. Return the indices of those two numbers, in any order. You may assume exactly one valid pair exists, and you may not use the same index twice.

Examples

▸ nums = [2, 7, 11, 15], target = 9

→ [0, 1]

▸ nums = [3, 2, 4], target = 6

→ [1, 2]

▸ nums = [3, 3], target = 6

→ [0, 1]

Progressive Hints

Hint 1 · Nudge

For each number, the thing you're hunting is its complement. Have you seen it before?

Hint 2 · Plan

Walk nums once, keeping a map from value to index. For each number, compute target minus number; if that complement is already in the map, return both indexes in any order. Otherwise store the current number with its index.

Hint 3 · Approach

seen = map from value to index. For each i, n: if (target - n) is in seen, return [seen[target - n], i]. Otherwise seen[n] = i.

Output

// Run your code to see the output here.