最接近的三数之和[中等][排序\双指针][三数之和改编]

标题

思路

是三数之和的思路的改编 三数之和[中等][双指针排序] – ()

具体步骤如下：

1. 将数组从小到大进行排序
2. (外层遍历)从小到大取数字nums[i], 设置target1为target-nums[i], (target1相当所以target – a), 然后从i+1 ~ nums.length-1的范围进行双指针的遍历, 设置begin = i + 1, end = nums.length – 1，开始进入内层遍历，进行判别
3. (内层遍历-核算偏移量)核算tmp = nums[begin] + nums[end], 将t=target1-tmp, t相当所以target – a – b – c, 即a+b+c和target的偏移量, 将之前的最小偏移量offset和t进行比较, 将绝对值小的赋值给offset
4. (内层遍历-移动begin和end)比较tmp和target，（即比较 b+c 和 target – a）。

   • 假如tmp小，则需求变大来贴近target - a, 因而begin++
     

   • 假如tmp大，则需求变小来贴近target - a, 因而end--
     

   • 假如二者相等，则证明b+c == target - a, 即a+b+c == target,能够直接退出循环。
     

解说 为什么能够经过排序然后经过begin和end指针来进行核算?

• 首先是经过第一层遍历，将三数之和的问题转化为两数之和接近于固定值的问题：转化为b+c 接近于target – a(第一层遍历的是a)
• 然后在第二层遍历里面，由于a之前的值现已作为 target- a来参加核算的进程，因而假如有最接近的答案，都现已记录下来了，因而不需求去遍历a前面的值来完成接近于target – a, 只需求遍历后边的值即可, 因而begin = a的index + 1, end = nums.length – 1

注意点:

• 在判别offset的最小值的时分，是判别的绝对值巨细，而不是值的巨细(由于有正数和负数)
• 在碰到offset为0的时分，能够直接退出循环然后输出答案(由于0表明的便是最接近了，不可能比他再接近)

代码

var closeTarget = function(nums, begin, end, target){
    let offset = target - nums[begin] - nums[end];
    while(begin < end){
        let tmp = nums[begin] + nums[end];
        let t = target - tmp;
        offset = offset*offset < t*t? offset: t;
        if(tmp < target){
            begin++;
        }else if(tmp > target){
            end--;
        }else{
            offset = 0;
            break;
        }
    }
    return offset;
}
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort((a, b)=> a-b);
    let min = closeTarget(nums, 1, nums.length - 1, target - nums[0]);
    for(let i = 1; i < nums.length - 2; i++){
        let tmp = closeTarget(nums, i + 1, nums.length - 1, target - nums[i]);
        min = tmp*tmp > min*min? min: tmp;
        if(min == 0){
            break;
        }
    }
    return target - min;
};