Javascript solution beats 100%


  • 0
    S
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    var threeSum = function(nums) {
        var results = [];
        
        if (!Array.isArray(nums) || nums.length < 3) {
            return results;
        }
        
        var map = {};
        var len = nums.length;
        for (var i = 0; i < len; i++) {
            map[nums[i]] = (map[nums[i]] || 0) + 1;
        }
        
        nums.sort(function (a, b) {
            return a - b;
        });
        for (i = 0; nums[i] <= 0 && i < len - 1; i++) {
            var nNum = nums[i];
            map[nNum]--;
            if (i > 0 && nNum === nums[i - 1]) {
                continue;
            }
            for (var j = len - 1; j > i && nums[j] >= 0; j--) {
                var pNum = nums[j];
                map[pNum]--;
                if (j < len - 1 && pNum === nums[j + 1]) {
                    continue;
                }
                var diff = 0 - nNum - pNum;
                if (map[diff] > 0) {
                    results.push([nNum, diff, pNum]);
                }
                if (diff >= pNum) {
                    j--;
                    break;
                }
            }
            
            for (++j; j < len; j++) {
                map[nums[j]] += 1;
            }
        }
        
        return results;
    };

  • 0
    S

    A summary of what it does:

    • Build a value to occurrence count map for the array, for look up of the 3rd integer. Occurrence count is to keep the map within the search scope.
    • Sort the array.
    • Search from both ends, and see if the 3rd integer(difference) exists in the map.
    • Keep the occurrence count up-to-date under all conditions.
    • Terminate the search prematurely and move on, based on the following conditions:

      negative number >= 0, position number <= 0, and difference (3rd number) >= positive number

Log in to reply
 

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