JavaScript solution O(n^2) two-pointer [Somehow beats 100% 104ms LOL]


  • 1
    R

    The code is not perfect, but it shows the idea of the algorithm.

    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    var threeSumClosest = function(nums, target) {
      var MAX_VALUE = 2147483647;
      
      if (nums.length < 3) return 0;
      nums.sort(function(a, b) { return a-b; }); 
      
      var i,
        len = nums.length,
        minDiff = MAX_VALUE,
        complement,
        p1,
        p2,
        curSum,
        result;
      
      for (i = 0; i < len - 2; i++) {
        complement = target - nums[i];
        p1 = i + 1;
        p2 = len - 1;
        while (p1 < p2) {
          curSum = nums[p1] + nums[p2];
          if (minDiff > Math.abs(curSum - complement)) {
            minDiff = Math.abs(curSum - complement);
            result = curSum + nums[i];
          }
          if (minDiff === 0) break;
          if (curSum > complement) {
            p2--;
          } else if (curSum < complement) {
            p1++;
          }
        }
        while (nums[i+1] === nums[i]) {
          i++;
        }
      }
      return result;
    };

Log in to reply
 

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