3Sum Closest

[barretlee]

本题难度：★★

给定一个长度为 n 整数数组 S，找出三个整数，使得三数之和最接近给定的一个目标数 target，返回这三数之和。

假定给定的 S 只有一个解，例如：

给定 S = [-1, 2, 1, -4], target = 1，与 target 最接近的三数和为 (-1 + 2 + 1 = 2)，输出 2.

[Min-field]

时间效率 O(n*n) , 算法参考自三数之后为定值

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort( (a, b) => a - b ); 

    let sum = 2 << 30; 

    for(let i = 0; i < nums.length - 2; i++){
        let low = i + 1, 
            high = nums.length - 1; 

        while(low < high){
            let termSum = nums[low] + nums[high] + nums[i], 
                diff = termSum - target; 

            if(Math.abs(diff) < Math.abs(sum - target))
                sum = termSum; 

            if(diff === 0)
                return sum; 
            else if (diff < 0)
                low ++; 
            else 
                high --; 
        }
    }
    return sum; 
};

let nums = [-1, 2, 1, -4], 
    target = 1; 

console.log(threeSumClosest(nums, target)); 

[barretlee]

function resolve(S, target) {
  S.sort((a, b) => a > b ? -1 : 1);
  var i = S.length - 1, closest = S[i - 2] + S[i - 1] + S[i], diff = Math.abs(target - closest);
  while(i--) {
    var l = i - 1, r = 0;
    while(l > r) {
      var sum = S[i] + S[l] + S[r], newDiff = Math.abs(target - sum);
      diff > newDiff && (diff = newDiff, closest = sum);
      sum < target ? --l : ++r;
    }
  }
  return closest;
}

console.assert(resolve([-1, 2, 1, -4], 1) === 2, 2);
console.assert(resolve([-1, 2, 1, -4], -10) === -4, -4);

[pixcai]

小胡子哥你的算法错了