Any improvement for JS solution?


  • 0
    T

    Want to find way to do O(n)

    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function(nums, target) {
        var length =nums.length;
        for(i=0;i<length;i++){
            for(j=i+1;j<length;j++){
                if(nums[i]+nums[j] == target){
                   var result = [i,j];
                   return result;
                }
            }
            
        }
    };
    

  • 0
    D

    There are two values needed to sum.

    You can loop through the list once and store the value needed given the number and the target.

    Given a target of  9 and a list [2, 7, 11, 15]
    
    At index 0, please store (9 - 2), which is 7, key:7 index:0 is stored in a Map()
    

    The key-value pair is map.set(target - nums[i], i). The difference needed to sum to target is stored as the key, and the index is stored as the value.

    As you iterate through, check if the current nums[i] value exists in the Map(). If it does, it means you have both pairs of values needed to reach the target sum.

    const twoSum = function(nums, target) {
    
        let map = new Map()
    
        for (let i = 0; i < nums.length; i++) {
            if (map.has(nums[i])) {
                return [map.get(nums[i]), i]
            }
            map.set( ( target - nums[i] ), i ) // required : index
        }
        throw new Error('No match.')
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.