This content originally appeared on DEV Community and was authored by DEV Community
You want to find 2 numbers that add up to the target and return their indices.
This is considered an easy interview problem, if you get it, god is watching over you.
Now, there are few ways to approach this: the brute force way (it'l work but it aint impressive), and then the optimal way. We will cover both.
The brute force way
Note: This will work, but make sure you can optimize it too.
The logic is as follows. We will use two for loops. The first will look through all the elements starting at the first element. Then next loop will go through all the elements starting at second element. If the two add up to the target, return the indicies of them. Relatively straightforward, but it takes up a lot of memory to run two for loops so it'l become more inefficient as the array grows. Nevertheless, here's the answer.
`var twoSum = function(nums, target) {
let result = []
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
result.push(i, j)
}
}
}
return result
}`
The efficient way
We don't want to use 2 for loops. Let's just use one.
What we'll do is create an empty object, and then we'll use forEach on the nums array. The forEach method can take in an element and its index, so we can set each set the element's index as the key and the element as its value.
`var twoSum = function(nums, target) {
let obj = {}
nums.forEach((num, index) => {
obj[num] = index
}
}`
Now we are going to loop through the nums array and use our one shot at a for loop.
var twoSum = function(nums, target) {
let obj = {}
nums.forEach((num, index) => {
obj[num] = index
}
for (let i = 0; i < nums.length; i++) {
let secondElement = target - element
if (obj[secondElement] !== undefined && obj[secondElement] !== index) {
return [index, secondElement]
}
}
}
If ewe example whats happening above, we're looping through the numbers in the nums array and were saying, does the result of the target number minus the current element exist as a number here? That is, if the target is 9 and our nums array is [2, 7, 13, 15], does 9 - 2 exist? or does 9 - 7 exist? And is it not an existing element (we can use the same number twice)?
If so, return the element, and then the secondElement i.e the result of the target element minus the current element.
This content originally appeared on DEV Community and was authored by DEV Community
DEV Community | Sciencx (2022-03-02T03:19:21+00:00) Two Sum Problem. Retrieved from https://www.scien.cx/2022/03/02/two-sum-problem/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.