-
Notifications
You must be signed in to change notification settings - Fork 18
/
01.TwoSum.js
51 lines (47 loc) · 1.53 KB
/
01.TwoSum.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
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.
*/
//brute force/naive approach Time complexity O(n^2) Space complexity O(1)
const twoSum = (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];
}
}
}
return [];
};
// Optimal soln1 Time complexity O(n) Space complexity O(n)
const twoSum1 = (nums, target) => {
const hash = {};
for (let i = 0; i < nums.length; i++) {
const n = nums[i];
if (hash[target - n] !== undefined) {
return [hash[target - n], i];
}
hash[n] = i;
}
return [];
};
//Optimal Soln2 Time complexity O(n) Space complexity O(1)
// Formulae ( missing target = target - current element)
const twoSum2 = (nums, target) => {
const map = nums.reduce((acc, current, idx) => {
acc[current] = idx;
return acc;
}, {});
for (let i = 0; i < nums.length; i++) {
const missingTarget = target - nums[i];
if (map[missingTarget]) {
return [i, map[missingTarget]];
}
}
};
console.log(twoSum([2, 7, 11, 15], 9)); // Outputs: [0,1]
console.log(twoSum([31, 10, 7, 9], 6)); // Outputs: [-1,-1]
console.log(twoSum([3], 7)); //Outputs: [-1, -1]
console.log(twoSum([], 20)); // Outputs: [-1, -1]]
console.log(twoSum([3, 3], 6)); // Outputs: [0,1]