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; O(n) expected over the O(n^2) brute force.

Example

• nums = [2,7,11,15], target = 9 → [0,1].

Expected approach

• One-pass hashmap value → index: for each x, if target − x is already in the map, done; else store x. O(n) time/space. Duplicates are handled naturally because the complement is checked before inserting the current element. Contrast: sort + two pointers is O(n log n) and loses original indices unless paired. Follow-ons to expect: input sorted (two pointers), count pairs, 3Sum.