The Problem
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Basic Solution
The brute force way of solving this would be looping through the array twice and adding up one number from each array to see if it equals the target. This is what it that looks like:
let twoSum = (nums, target) => {
for(var i = 0; i < nums.length; i++) {
for(var j = i + 1; j < nums.length; j++) {
if(nums[i] + nums[j] == target) {
return [i,j]
}
}
}
}
This is inefficient simply because we have to do double the amount of work when looping through the same array twice. Although this will always work, as the array gets larger, the execution gets exponentially slower.
So let's take a look at how to go through this array only once.
Efficient Solution
First off, we need a way to keep track of all of the numbers we've already looked at as well as what numbers we need. We're going to do this by using a prevValues object to store our values which allows us to look at our numbers instantly without having to loop through the array again to see if the number exists. Take a look:
let twoSum = (nums, target) => {
// Create object to store values
const previousValues = {}
for (let i = 0; i < nums.length; i++) {
const currentValue = nums[i]
const neededValue = target - currentValue
// Store needed value as a key in the object
const index2 = previousValues[neededValue]
// Check if we have an index that is equal to our needed value
if (index2 != null) {
return [index2, i]
} else {
// Store index for current value
previousValues[currentValue] = i
}
}
}
Top comments (0)