I am implementing a hash map for the Two Sum leetcode problem.
const testArrs = {
'first': [2,7,11,15],
'second': [3,2,4],
'third': [3,3]
}
function twoSum(nums, target) {
let mapped = nums.map((item) => target - item);
let returnedArr = mapped.filter((item) => {
if (nums.includes(item)) {
console.log(nums.indexOf(target-item))
return nums.indexOf(target - item)
}
})
console.log(returnedArr)
//TODO check if returnedArr size == 2.
}
twoSum(testArrs['first'], 9)
The first array mapped creates an array of hashes as "indexes" that are the difference of target from each element in the nums array. Then I apply a filter to the mapped array to see if 2 elements of the mapped array are contained in the nums array, returning the index of those elements.
When the indexes are filtered into the returnedArr it seems to return the first element of nums instead of two indexes. [2] instead of [0,1] The logging before the return shows it is correctly registering indexes 0 and 1 respectively.
Thats because youre mixing the filter with the the map function. The map function must return a boolean (which will create an array of the targets which comply with the condition). And, after getting those values, in your case, the ones that are contained in the nums, you map them to get their index. Like this:
const testArrs = {
'first': [2,7,11,15],
'second': [3,2,4],
'third': [3,3]
}
function twoSum(nums, target) {
let mapped = nums.map((item) => target - item);
let returnedArr = mapped.filter((item) => {
return nums.includes(item)
})
return returnedArr.map((item)=> nums.indexOf(target-item))
}
console.log(twoSum(testArrs['first'], 9))`
Basically return nums.indexOf(target - item) results to false if the index is 0. Instead, you need to check if nums.indexOf(target - item) >= 0.
However, Array#filter isn't really what you're looking for:
The filter() method creates a new array with all elements that pass the test implemented by the provided function.
Instead, you need to use a Map to save the number-index pairs, and then check if a complement is in the Map:
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], i);
}
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement) && map.get(complement) != i) {
return [i, map.get(complement)];
}
}
}
const testArrs = { 'first': [2,7,11,15], 'second': [3,2,4], 'third': [3,3] };
console.log( twoSum(testArrs['first'], 9) );A faster way would be doing it in one iteration:
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
}
const testArrs = { 'first': [2,7,11,15], 'second': [3,2,4], 'third': [3,3] };
console.log( twoSum(testArrs['first'], 9) );