最接近的三数之和

来源Leetcode第16题最接近的三数之和

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

思路与上一题类似，但是我在做题的时候掉进了nums[i] == target这个坑，加之与坤滨一席话，让我久久没有从坑里出来。
思路来自题解

• 1.排序
• 2.在数组 nums 中，进行遍历，每遍历一个值利用其下标k，形成一个固定值 nums[k]
  两个指针， 左边起点为 left = k + 1 ，右边终点 right = nums.length - 1 处
• 3.因为数组已经排序，故在 [left, right]区间内，最大值 rangeMax = nums[k] + nums[right] + nums[right - 1],
• 4.最小值为 rangeMin = nums[k] + nums[left] + nums[left + 1];
• 5.如果最大值比target还大，或者最小值比target还小，则整个区间就没必要循环下去了。
• 6.如果不是，就是正常的双指针找法。
• 7.根据 sum = nums[left] + nums[right] + nums[k] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 min
• 8.同时判断 sum 与 target 的大小关系，因为数组有序，如果 sum > target 则 right—，如果 sum < target 则 right++，如果 sum == target 直接返回结果

代码如下：

public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int result = Integer.MAX_VALUE, left, right, min = Integer.MAX_VALUE;
        for (int k = 0; k < nums.length - 2; k++) {
            left = k + 1;
            right = nums.length - 1;

            // 区间[left,right]内,和最小的值
            int rangeMin = nums[k] + nums[left] + nums[left + 1];
            // 区间[left,right]内,和最大的值
            int rangeMax = nums[k] + nums[right] + nums[right - 1];
            if (rangeMin > target) {
                // 区间最小值比目标大, 没必要寻找区间其他值的和了
                if (rangeMin - target < min) {
                    min = rangeMin - target;
                    result = rangeMin;
                }
            } else if (rangeMax < target) {
                // 区间最大的值比目标还要小,也没必要寻找区间其他值的和了
                if (target - rangeMax < min) {
                    min = target - rangeMax;
                    result = rangeMax;
                }
            } else {
                while (left < right) {
                    int sum = nums[left] + nums[right] + nums[k];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        return sum;
                    }
                    if (Math.abs(sum - target) < min) {
                        result = sum;
                        min = Math.abs(sum - target);
                    }
                }
            }
        }
        return result;
    }