16.最接近的三数之和

题目:最接近的三数之和

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

• 示例 1：

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

• 示例 2：

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

• 提示：

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

思路

1.先固定一个数i,然后对另外两个数使用双指针,
2.利用Arrays.sort(nums)对数组进行排序。
3.初始化一个用于保存结果的值result = nusm[0] + nums[1] + nums[2]
4.利用下标i对数组进行遍历，此时就是在固定第一个元素
5.每次遍历的过程中设置两个指针，分别是left = i + 1、right = nums.length - 1。
6.检查sum = nums[i] + nums[left] + nums[right]与target的距离，如果该距离比之前保存的 result与target的距离更小，就更新result。
7.然后就是移动双指针。
8.如果sum的值比target大，那么我们让right--，因为数组是有序的，right--会使得下一次的 sum更小，也就更接近target的值
9.同理，如果sum的值target小，那么我们让left++。
10.left++和right--的界限自然是left < right，如果left == right，说明我们已经将所有的元素都遍历过一遍了。
重复上面的操作，直到i循环结束为止，返回result。
有些时候，可能会直接找到三数之和等于target的情况，此时直接返回结果即可，不需要在进行之后的循环，因为不可能有数比他自己更接近自己了

• 时间复杂度:O(n²)
• 空间复杂度:O(1)

代码

public int threeSumClosest(int[] nums, int target) { // 总时间复杂度O(n²)
    Arrays.sort(nums);
    int result = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length; i++) { // 时间复杂度O(n²)
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) { // 时间复杂度O(n)
            // 获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏
            int min = nums[i] + nums[left] + nums[left + 1];
            if (target < min) {
                if (Math.abs(result - target) > Math.abs(min - target)) {
                    result = min;
                }
                break;
            }
            // 获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略
            int max = nums[i] + nums[right] + nums[right - 1];
            if (target > max) {
                if (Math.abs(result - target) > Math.abs(max - target)) {
                    result = max;
                }
                break;
            }
            int sum = nums[i] + nums[left] + nums[right];
            // 判断三数之和是否等于target
            if (sum == target) {
                return sum;
            }
            if (Math.abs(result - target) > Math.abs(sum - target)) {
                result = sum;
            }
            if (sum < target) {
                // 当左指针扫描到与上一个相等的时候,直接跳过
                while (left < right && nums[left] == nums[++left]) {
                }
            } else {
                // 当右指针扫描到与上一个相等的时候,直接跳过
                while (left < right && nums[right] == nums[--right]) {
                }
            }
        }
    }
    return result;
}