EasyReturn indices of the two numbers that add up to a target.
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution and you may not use the same element twice.
Walkthrough
try:
1
function twoSum(nums, target) {
2
const seen = new Map();
◄
3
for (let i = 0; i < nums.length; i++) {
4
const need = target - nums[i];
5
if (seen.has(need))
6
return [seen.get(need), i];
7
seen.set(nums[i], i);
8
}
9
}
no locals yet
array
3
0
2
1
4
2
seen (value → index)
(empty)
STEP 0 / 11 · line 2
Start
Create an empty map of value → index. We walk the array once.
Intuition
The brute-force scan of every pair is O(n²). We can do better by remembering what we have already seen.
As we walk the array, for the current value n the partner we need is target − n.
A hash map from value → index lets us check in O(1) whether that partner appeared earlier.
The algorithm
01Create an empty map of value → index.
02For each element n at index i, compute need = target − n.
03If need is already in the map, return [map[need], i].