'Javascript twoSum algorithm: Given an array of integers, return indices of the two numbers such that they add up to a specific target
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
Example:
Given nums =
[3, 2, 4], target = 6,Because
nums[1] + nums[2]= 2 + 4 = 6
return [1, 2].
Solution
var twoSum = function(nums, target) {
for(let i = 0; i <= nums.length; i++){
for(let j = 0; j <= nums.length; j++){
if(nums[i] + nums[j] == target){
return [i, j]
}
}
}
};
The code above works in other cases but not this one.
Expected result [1,2]
Output [0,0]
For instance, I've tried to use a different array of numbers and a different target and it works even if you change the order of the numbers
Example:
New array: [15, 7, 11, 2], target = 9,
Output: [1, 3].
I don't understand what is wrong with the solution and I hope that someone can explain. Thanks
Solution 1:[1]
I don't understand what is wrong with the solution and I hope that someone can explain ?
Here you're both inner and outer loop start from 0th so in the case [3,2,4] and target 6 it will return [0,0] as 3 + 3 is equal to target, so to take care of same index element not being used twice created a difference of 1 between outer and inner loop
Make outer loop to start from 0th index and inner loop with value i+1
var twoSum = function(nums, target) {
for(let i = 0; i < nums.length; i++){
for(let j = i+1; j < nums.length; j++){
if(nums[i] + nums[j] == target){
return [i, j]
}
}
}
};
console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))Solution 2:[2]
You can use a very simple technique.
Basically, you can check if the difference of target & the element in the current iteration, exists in the array.
Assuming same index cannot be used twice
nums = [3, 2, 4], target = 6
nums[0] = 3
target = 6
diff = 6 - 3 = 3
nums.indexOf[3] = 0 // FAILURE case because it's the same index
// move to next iteration
nums[1] = 2
target = 6
diff = 6 - 2 = 4
nums.indexOf(4) = 2 // SUCCESS '4' exists in the array nums
// break the loop
Here's the accepted answer by the leetcode.
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for (let index = 0; index < nums.length; index++) {
const diff = target - nums[index];
const diffIndex = nums.indexOf(diff);
// "diffIndex !== index" takes care of same index not being reused
if (diffIndex !== -1 && diffIndex !== index) {
return [index, diffIndex];
}
}
};
Runtime: 72 ms, faster than 93.74% of JavaScript online submissions for Two Sum.
Memory Usage: 38.5 MB, less than 90.55% of JavaScript online submissions for Two Sum.
Can anybody help me in reducing the memory usage also?
Solution 3:[3]
we can solve this problem in O(n) by using the map/object. We can maintain a map or object which will save all values with index and then we can iterate the array and find target-nums[i] for each value and will find that value in map/object. let's see this by example:-
nums=[2,7,11,15]
target = 9;
then map/object will be
mm={
2 : 0,
7: 1,
11: 2,
15: 3
}
then for each value, we will find diff and find that diff in map/object.
for i=0 diff= 9-2=7 and mm.has(7) is true so our answer is 2 and 7.
for their index we can use mm.get(7) and i.
return [mm.get(7), i]
var twoSum = function(nums, target) {
let mm=new Map();
for(let i=0;i<nums.length;i++){
mm.set(nums[i],i);
}
let diff=0;
let j;
for(let i=0;i<nums.length;i++){
diff=target-nums[i];
if(mm.has(diff) && i!=mm.get(diff)){
j=mm.get(diff);
if(j>i){
return [i,j];
}else{
return [j,i];
}
}
}
};Runtime: 76 ms, faster than 88.18% of JavaScript online submissions for Two Sum. Memory Usage: 41.4 MB, less than 13.32% of JavaScript online submissions for Two Sum.
Solution 4:[4]
var twoSum = function(nums, target) {
for(let i=0; i<nums.length; i++){
for(let j=i+1; j<nums.length; j++){
if(nums[j] === target - nums[i]){
return [i, j];
}
}
}
};
Solution 5:[5]
Your solution works as expected. For nums = [3, 2 ,4] and target = 6, [0, 0] is a valid solution for the outlined problem as nums[0] + nums[0] = 3 + 3 = 6.
If you need two different indices (In my understanding this is not required by the task) you can add an additional check for inequality (nums[i] + nums[j] == target && i != j).
Solution 6:[6]
var twoSum = function (nums, target) {
var len = nums.length;
for (var i = 0; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (nums[i] + nums[j] == target) {
return [i,j];
}
}
}
};
Solution 7:[7]
var twoSum = function(nums, target) {
for(var i=0;i<nums.length;i++){
for(var j=i+1;j<nums.length;j++){
temp = nums[i]+nums[j];
if(temp == target){
return [i,j]
}
}
}
};
console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))
console.log(twoSum([3,3],6))
This works perfectly and the Runtime: 72 ms lesser than 84ms
Solution 8:[8]
Another efficient solution way to solve this problem with an O(n) time complexity is not using nested loops. I commented the steps, so JS developers can easy understand. Here is my solution using golang:
func twoSum(intArray []int, target int) []int {
response := []int{-1, -1} // create an array as default response
if len(intArray) == 0 { // return default response if the input array is empty
return response
}
listMap := map[int]int{} // create a Map, JS => listMap = new Map()
for index, value := range intArray { // for loop to fill the map
listMap[value] = index
}
for i, value := range intArray { // for loop to verify if the subtraction is in the map
result := target - value
if j, ok := listMap[result]; ok && i != j { // this verify if a property exists on a map in golang. In the same line we verify it i == j.
response[0] = i
response[1] = j
return response
}
}
return response
}
Solution 9:[9]
var twoSum = function(nums, target) {
var numlen = nums.length;
for(let i=0; i<=numlen; i++){
for(let j=i+1;j<numlen;j++){
var num1 = parseInt(nums[i]);
var num2 = parseInt(nums[j]);
var num3 = num1 + num2;
if(num3 == target){
return[i,j]
}
}
}
};
Solution 10:[10]
I suppose this could be a better solution. Instead of nesting loops, this provides a linear solution.
(PS: indexOf is kinda a loop too with O(n) complexity)
var twoSum = function (nums, target) {
const hm = {}
nums.forEach((num, i) => {
hm[target - num] = i
})
for (let i = 0; i < nums.length; i++) {
if(hm[nums[i]] !== undefined && hm[nums[i]] !== i) {
return ([hm[nums[i]], i])
}
}
};
Solution 11:[11]
var twoSum = function(nums, target) {
for (var i = 0; i < nums.length; i++)
{
if( nums.indexOf(target - nums[i]) !== -1)
{
return [i , nums.indexOf(target - nums[i])]
}
}
};
Solution 12:[12]
For clearity console a & b in inner for loop . This will give you clear insight
var twoSum = function(nums, target) {
var arr=[];
for(var a=0;a<nums.length;a++){
for(var b=1;b<nums.length;b++){
let c=nums[a]+nums[b];
if(c== target && a != b){
arr[0]=a;
arr[1]=b;
}
}
}
return arr;
};
Solution 13:[13]
My solution:
- Create a Set
- Then loop the array for retrieve all the differences between the target number minus all the elements in array. Insert only which are positive (as is a Set, duplicates will not be included).
- Then iterates array again, now only compare if array elements is in the set, if yes take the index from i store in the index array and return it.
public static Object solution(int[] a, int target){
Set<Integer> s = new HashSet<>();
ArrayList<Integer> indexes = new ArrayList<Integer>();
for (int e : a){
Integer diff = new Integer(target - e);
if(diff>0){
s.add(diff);
}
}
int i = 0;
for (int e : a){
if(s.contains(e)){
indexes.add(i);
}
i++;
}
return indexes;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow