Two Sum

Problem Given an array of integers and a target value x, find two elements that sum to x. Do it in a single pass, in O(n) time.

Input / Output

• Input: array arr of n integers, and target x.
• Output: the pair of values (or their indices) that sum to x; some variants ask for all such pairs, others only whether one exists.

Constraints

• Single pass, O(n) time.
• Values may be negative and may repeat.
• An element may not be paired with itself at the same index.
• Clarify whether indices or values are wanted, and whether duplicate pairs should be reported once or every time.

Example

• arr = [2,7,11,15], x = 9 → (2,7).
• arr = [3,3], x = 6 → (3,3) at indices 0 and 1 — legal, two distinct positions.
• arr = [3,2,4], x = 6 → (2,4), not (3,3): the single 3 must not pair with itself.