Description
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]
Constraints:
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- Only one valid answer exists.
Approach
Given the following assumptions:
- Only two numbers add up to the target.
- Only one valid answer exists.
We can use a Map to keep track of the numbers we have traversed.
During the traversal, we check if there is a matching number(complement) in the Map. If there is, it is the correct answer.
Solution
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
// Create a map to store the indices of the numbers we've seen so far
const indexMap = {};
for (let currentIndex = 0; currentIndex < numbers.length; currentIndex++) {
// Calculate the complement that would add up to the target with the current number
const complement = target - numbers[currentIndex];
// Check if the complement exists in the map
if (indexMap.hasOwnProperty(complement)) {
// If it exists, return the indices of the complement and the current number
return [indexMap[complement], currentIndex];
}
// Otherwise, add the current number and its index to the map
indexMap[numbers[currentIndex]] = currentIndex;
}
// If no solution is found, return an empty array (although the problem guarantees one solution)
return [];
};
Complexity Analysis
Time Complexity
The time complexity is O(n) because we traverse the array once.
Space Complexity
The space complexity is O(n) because we store the indices of the numbers in the map.