Arrays & Hashing · 001Easy
Two Sum
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target. Exactly one valid answer exists, and you may not use the same element twice.
Constraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- Exactly one valid answer exists.
Examples
twoSum([2, 7, 11, 15], 9) -> [0, 1] // 2 + 7 === 9 twoSum([3, 2, 4], 6) -> [1, 2] twoSum([3, 3], 6) -> [0, 1] // duplicates are allowed twoSum([-3, 4, 3, 90], 0) -> [0, 2] // negatives twoSum([0, 4, 3, 0], 0) -> [0, 3] // a zero pair, not [i, i] twoSum([-1, -2, -3, -4, -5], -8) -> [2, 4] // all negative
Edge cases
- Duplicate values that form the answer ([3,3]).
- Negative numbers.
- The answer is never
[i, i]— an element cannot be reused. - FOLLOW-UP
- Can you come up with an algorithm that is less than O(n^2) time complexity?
Show the target complexity (spoiler)
- Naive
- O(n^2) time, O(1) space — test every pair with nested loops.
- Target
- O(n) time, O(n) space — one pass, storing `value -> index` in a hash map and looking up `target - value`.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/001-two-sum.js ./practice c 001