Two sum

Problem Given an integer array and a target, return the indices of the two numbers summing to the target. Exactly one solution exists; the same element can't be used twice.

Input / Output

• Input: int array nums, int target.
• Output: the two indices (any order).

Constraints

• n up to 10^4; values may be negative.
• An O(n) solution is expected over the O(n^2) brute force.

Example

• nums = [2,7,11,15], target = 9 → [0,1].
• nums = [3,3], target = 6 → [0,1] (a duplicate value is a valid pair).