leetcode 16. 最接近的三数之和

题目描述

给定一个包括个整数的数组和 一个目标值。找出 中的三个整数，使得它们的和与最接近。返回这三个数的和。假定每组输入只存在唯一答案。
相关话题： 数组、双指针    难度： 中等
例如，给定数组, 和 .
与最接近的三个数的和为. .
思路：
这道题的解法和三数之和的双指针解法一样，相对两数之和，三数是一种降维操作。
与其说双指针，不如说是三指针，该题用到三个指针left、mid、right，
首先对数组进行从小到大的排序，

• left指针初始指向0位置，mid = left + 1，right指向最后一个位置。
• 大体思路是，固定left指针后，mid和right指针会向中间靠拢遍历数组，至于mid和right的更新则是通过当前三数的和与target比较确定更新mid还是right。
  直观地，当前和tmp > target时，为了让tmp变小，更新right指针(right--)，否则mid++
• mid和right相遇，内循环跳出，更新left指针，重新初始化mid和right，再做第二步地操作。
  
  
• 正确解法

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums.length < 3) return 0;
        Arrays.sort(nums);
        int left = 0, mid = 0, right = 0;
        int res = nums[0] + nums[1] + nums[2];
        for(left = 0;left < nums.length;left++){
            mid = left + 1;
            right = nums.length - 1;
            while(mid < right){
                int tmp = nums[left] + nums[mid] + nums[right];
                if(Math.abs(tmp - target) < Math.abs(res - target)){
                    res = tmp;
                }
                if(tmp > target){
                    right--;
                }else{
                    mid++;
                }
            }
        }
        return res;
    }
}

• bug记录
  刚开始居然以if(Math.abs(tmp - target) > Math.abs(res - target))这个条件来更新mid指针和right指针，这是不对的，因为tmp有可能比target大，也有可能比target小，所以根据tmp到target的距离来判断更新mid和right指针是不对的，应该根据tmp和target的大小更新。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums.length < 3) return 0;
        Arrays.sort(nums);
        int left = 0, mid = 0, right = 0;
        int res = nums[0] + nums[1] + nums[2];
        for(left = 0;left < nums.length;left++){
            mid = left + 1;
            right = nums.length - 1;
            while(mid < right){
                int tmp = nums[left] + nums[mid] + nums[right];
                if(Math.abs(tmp - target) > Math.abs(res - target)){
                    right--;
                }else{
                    res = tmp;
                    mid++;
                }
            }
        }
        return res;
    }
}