two-sum algorithm

Question

Can someone help me in optimizing the code here?

This is the original question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Question link: https://leetcode.com/problems/two-sum/

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const hashMapArray = {}
    for (let i=0; i<nums.length; i++) {
        const num = nums[i]
       for (let index in hashMapArray) {
           if (hashMapArray[index] + num  === target) {
               return [index, i]
           }
       }
       hashMapArray[i] = num
    }
    return []
}

Frankly, I was expecting my code to be optimized but then this what I got as a result and I was kinda heartbroken

How can I make it better?

Results:

Answer 1

I can not work out why you are iterating the mapped values. The point of mapping the values is so you do not need to search them.

Rather than use an object to map the values you can also use a Map, though there is not much of a performance gain.

The following at most will only iterate each item once and thus save you a significant amount of CPU time.

function twoSum(nums, target) {
    const map = new Map(), len = nums.length;
    var i = 0;
    while (i < len) {
        const num = nums[i], val = target - num;
        if (map.has(val)) { return [i, map.get(val)] }
        map.set(num, i);
        i++;
    }
    return [];
}

To save memory you can use the following. It will be slower than the above function however it will still be a lot faster than your function as the inner loop only search from the outer loops current position.

function twoSum(nums, target) {
    const len = nums.length;
    var i = 0, j;
    while (i < len) {
        const val = target - nums[i];
        j = i + 1;
        while (j < len) {
            if (nums[j] === val) { return [i, j] }
            j++;
        }
        i++;
    }
    return [];
}

Answer 2

@iRohitBhatia your original solution creates an hash map without needing it and repeats the "sum" operation in the 2nd iteration also without need.

Here you have the Swift version I did code to solve it initially:

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    for i in 0..<(nums.count-1) {
        let matchValue = target - nums[i]

        for j in (i+1)..<nums.count {
            if nums[j] == matchValue {
                return [i, j]
            }
        }
    }

    return []
}

which I then translated to this JavaScript code:

var twoSum = function(nums, target) {
    for (let i = 0; i < (nums.length - 1); i++) {
        let matchValue = target - nums[i];

        for (let j = i+1; j < nums.length; j++) {
            if (nums[j] == matchValue) {
                return [i, j];
            }
        }
    }

    return [];
};

and after submitting it on LeetCode I got the following results: