Two Sum

Given an array of integers nums and an integer target, return the 0-indexed positions of the two numbers that add up to target. Each input has exactly one solution.

Example

Input: nums = 2 7 11 15, target = 9 Output: 0 1

Approach

Single pass with a hash map of value → index. For each number, check whether target - number was already seen — if so, you have your pair, in O(n) instead of O(n²).

Walkthrough

1for i, num in enumerate(nums):
2    complement = target - num
3    if complement in seen:
4        return seen[complement], i
5    seen[num] = i

Input format

Line 1: the array, space-separated Line 2: target