Two Sum

Problem

You are given an array of integers nums and an integer target. Return the indices of two distinct elements whose values add up to target. Exactly one such pair exists, and you may return the indices in any order.

• The array holds between 2 and 20,000 integers.
• Values and target are within a billion of zero in either direction.
• Exactly one pair of indices satisfies the requirement (this guarantee is what lets the solution return early).

Examples

• nums = [5, 1, 8, 4, 12], target = 12 → [2, 3], because 8 + 4 = 12.
• nums = [6, 6, 3], target = 12 → [0, 1]. Using index 0 twice would be invalid; the two indices must differ, but equal values at different positions are fine.
• nums = [-4, 9, 2, -7], target = -11 → [0, 3], since -4 + -7 = -11. Negative values need no special handling.

Hints

1. For each element, what single value would you need to find somewhere else in the array?
2. Checking "have I already seen value v" should not require scanning the array again.
3. One pass with a hash map from value to index is enough.