Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
- Input: nums = [2,7,11,15], target = 9
- Output: [0,1]
- Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
- Input: nums = [3,2,4], target = 6
- Output: [1,2]
Example 3:
- Input: nums = [3,3], target = 6
- Output: [0,1]
Sample Input
nums = [2,7,11,15], target = 9
Sample Output
[0,1]
Constraints
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
Follow-up
- What if the input array is sorted? (Can you do it in O(1) space?)
- What if you need to return the values instead of indices?
Test Cases
Case 1
Args: [[2,7,11,15],9]
Expected: [0,1]
Case 2
Args: [[3,2,4],6]
Expected: [1,2]
Case 3
Args: [[3,3],6]
Expected: [0,1]
Topics
Approach: Hash Map
For each number, check if target - num exists in a map of value → index. If it does, return the two indices. Otherwise store the current value and its index.
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (map.has(need)) return [map.get(need), i];
map.set(nums[i], i);
}
return [];
}
Time: O(n), Space: O(n).
Saved in this browser only. Private to you.