Two Sum

Problem Given an integer array and a target, return the indices of the two numbers that sum to the target. Exactly one solution exists and an element may not be reused.

Input / Output

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

Constraints

• 2 ≤ n ≤ 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].