Thoughts on JS solution?


  • 0
    A

    If seems a bit convoluted in my opinion but it's what I came up with. Seems there is no better than n^2 based on the posts.

    var threeSum = function(nums) {
    
        //Sort them to make this problem easier
        nums = nums.sort(
            function(a,b){
                return a - b
            }
        );
        
        //After it's sorted, get the index of the first element
        //that is greater or equal to the sum we want which is 0.
        //We will be looping around this element
        var splitIndex = getSplitIndex(nums, 0);
        
        //Some quick checks for error or fringe cases
        if(nums.length < 3){
            return [];
        }
        if(splitIndex === 0){
            if(nums[1] === 0 && nums[2] === 0){
                return [[0,0,0]];
            }
            else{
              return [];    
            }
        }
        var sols = new Array();
        
        //Check for this condition since my main loop will not find it
        if(nums[splitIndex] === 0  && nums[splitIndex+1] === 0 && nums[splitIndex+2] === 0){
            sols.push([0,0,0]);
        }
        
        //i will be our first pointer, and will start at the splitIndex value
        for(var i = 0; i < nums.length - splitIndex; i++){
            var s1 = nums[splitIndex + i];
            
            //j will be our second pointer, which will start at 0 and 
            // end before our current splitIndex
            for(var j = 0; j < splitIndex; j++){
                var s2 = nums[j];
                var sum = s1 + s2;
                
                // Once we have the sum of the first 2 pointers, we simply
                // want to look if this sum*-1 exists in this array, which
                // means we have a 3 sum that adds to 0
                var indexOfSum = nums.indexOf(-1 * sum);
                var solutionFound = (indexOfSum > -1 && indexOfSum !== i + splitIndex && indexOfSum !== j) ? true: false;
                
                // If it does exist, we create the array to add to sols,
                // but we first check if this array isn't already in sols
                // If no solution exists, we simply move the j pointer forward
                if(solutionFound === true){
                  var s3 = nums[indexOfSum];
                  var tempArr = [s1, s2, s3];
                  
                  tempArr = tempArr.sort(
                      function(a,b){
                        return a - b
                      }
                  );
                  
                  var matchInSols = sols.find(
                      function(element){
                        return element.toString() === tempArr.toString();
                      }
                  );
                  
                  if(typeof matchInSols === "undefined"){
                      sols.push(tempArr);  
                  }  
                  solutionFound = false;
                }
            }
        }
        return sols;
    };
    
    var getSplitIndex = function(nums, val){
        for(var i = 0; i < nums.length; i++){
            if(nums[i] >= val){
                return i;
            }
        }
    };
    

Log in to reply
 

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