最接近的三数之和

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

• 3 <= nums.length <= 10^3
• -10^3 <= nums[i] <= 10^3
• -10^4 <= target <= 10^4

题目要求找到与 target 最接近的三元组，我们可以直接使用三重循环枚举三元组 时间复杂度O(n^3)。我们首先枚举第一个元素 a ，对于剩下的两个元素 b 和 c ，希望它们的和能最接近 target - a。对于 b 和 c ，如果数组无序则只能使用两层循环枚举，当数组有序时则可以使用双指针优化。

左指针指向元素 a 右侧第一个元素，右指针指向数组最后一个元素（最大的元素）。

我们计算每一次遍历时 a + b + c 的值 temp，对于 temp 我们有两种情况：

• temp > target：数组的和较大，右指针左移
• temp < target：数组的和较小，左指针右移

在左右指针移动的过程中 左指针必须在右指针左侧，且指针下一次指向的值不能与上一次指向的值相同，这是为了避免结果重复。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        //排序
        Arrays.sort(nums);
        int best = 100000, n = nums.length;
        
		//遍历元素 a 
        for(int a = 0; a < n; a++){
            //必须与上一次遍历的元素不同
            if(a > 0 && a < n && nums[a] == nums[a - 1]){
                continue;
            }

            for(int b = a + 1, c = n - 1; b < c; ){
                //三个元素之和等于 target 直接返回
                int temp = nums[a] + nums[b] + nums[c];
                if(temp == target){
                    return temp;
                }
				
                //更新最接近 target 的值
                if(Math.abs(best - target) > Math.abs(temp - target)){
                    best = temp;
                }
				
                if(temp > target){
                    //右指针左移
                    --c;
                    //必须与上次遍历的元素不同
                    while(c > b && nums[c] == nums[c + 1]){
                        --c;
                    }
                }else{//左指针右移
                    ++b;
                    //必须与上次遍历的元素不同
                    while(b < c && nums[b] == nums[b - 1]){
                        ++b;
                    }
                }
            }
        }
        return best;
    }
}

时间复杂度O(n^2)，空间复杂度O(logN)，快排需要空间。