Finding Target Sum Of Three Numbers - Optimizing Nested Loops

I have a problem where, given an array of integers, I need to find sets of three numbers that add up to equal zero. The below solution works but isn't as optimal as I'd like and I

Solution 1:

One obvious optimisation is to precalculate the sum of the two first numbers just before the third nested loop. Then compare in the third loop if that number equals the opposite of the third iterated number.

Second optimisation is to take advantage of the fact that your items are sorted and use a binary search for the actual negative of the sum of the two first terms in the rest of the array instead of the third loop. This second optimisation brings complexity from O(N3) down to O(N2LogN)

Which leads to the third optimisation, for which you can store in a map the sum as key and as value, an array of the different pairs which sum to the sum so that each time you want to operate the binary search again, first you check if the sum already exists in that map and if it does you can simply output the combination of each pair found at that sum’s index in the map coupled with the negative sum.

Solution 2:

The OP's solution runs in O(N³) time with no additional storage.

The classic "use a hash table" solution to find the missing element can bring that down to O(N²) time with O(N) storage.

The solution involves building a number map using an object. (You could use a Map object as well, but then you can't be as expressive with ++ and -- operators). Then just an ordinary loop and inner loop to evaluate all the pairs. For each pair, find if the negative sum of those pairs is in the map.

functionthreeSum(nums) {

    var nummap = {};    // map a value to the number of ocurrances in numsvar solutions = newSet(); // map of solutions as strings// map each value in nums into the number map
    nums.forEach((val) => {
        var k = nummap[val] ? nummap[val] : 0; // k is the number of times val appears in nummap
        nummap[val] = k+1; // increment by 1 and update
    });

    // for each pair of numbers, see if we can find a solution the number mapfor (let i = 0; i < nums.length; i++) {

        var ival = nums[i];
        nummap[ival]--;

        for (let j = i+1; j < nums.length; j++) {
            var jval = nums[j];
            nummap[jval]--;

            var target = -(ival + jval); // this could compute "-0", but it works itself out since 0==-0 and toString will strip the negative off// if target is in the number map, we have a solutionif (nummap[target]) {

                // sort this three sum solution and insert into map of available solutions// we do this to filter out duplicate solutionsvar tmp = [];
                tmp[0] = ival;
                tmp[1] = jval;
                tmp[2] = target;

                tmp.sort();
                solutions.add(tmp.toString());
            }

            nummap[jval]++; // restore original instance count in nummap
        }
        nummap[ival]--;
    }

    for (s of solutions.keys()) {
        console.log(s);
    }

}

threeSum([9,8,7,-15, -9,0]);

Solution 3:

var threeSum = function(unsortedNums) {
    const nums = unsortedNums.sort();

    if(nums.length && (nums[0] > 0 || nums[nums.length-1] < 0)) {
        return [];
    }

    const result = newMap();

    for(let i=0; i < nums.length; i++) {
        for(let z=i+1; z < nums.length; z++) {
            for(let q=z+1; q < nums.length; q++) {
                if(nums[i]+nums[z]+nums[q] === 0) {
                    const toAdd = [nums[i], nums[z], nums[q]];            
                    const toAddStr = toAdd.join(',');

                    if(!result.has(toAddStr)) {
                        result.set(toAddStr, toAdd);
                    }
                }
            }
        }
    }

    returnArray.from(result.values());
};