Solutions to LeetCode's 1. Two Sum with JavaScript.
Solution 2 also addresses the following follow-up.
Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?
An easy one to come up with is a nested for loop.
Solution 1: Nested for loop
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
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];
}
}
}
};
- Time complexity: O(n^2)
- Space complexity: O(1)
This solution has O(n^2) time complexity because of nesting loops, so I want to find another way.
Solution 2:Using object
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = (nums, target) => {
const hash = {};
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (hash[complement] !== undefined) {
return [i, hash[complement]];
}
hash[nums[i]] = i;
}
};
- Time complexity: O(n)
- Space complexity: O(n)
Store the nums value in the keys of the hash and the index in the value.
hash[nums[i]] = i;
Then, in each loop, check whether the target minus the nums value exists in the hash.
If it exists, it returns the index of the current loop and the value of the matching hash (index of the stored nums).
const complement = target - nums[i];
if (hash[complement] !== undefined) {
return [i, hash[complement]];
}
In many cases, we want to avoid Time complexity: O(n^2), so I think solution 2 using hash is better.
Top comments (0)