leetcode 16. 最接近的三数之和（Java版）

题目描述（题目难度，中等）

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

例如，给定数组 nums = [-1，2，1，-4] 和 target = 1.
与 target 最接近的三个数的和为 2 (-1 + 2 + 1 = 2)。

示例代码

时间复杂度为

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 排序
        // 遍历
        // 寻找当前元素后面的最接近的两数之和
        //      双指针算法，等于就输出，否则就向中间移动直至相遇
        Arrays.sort(nums);
        int closest = Integer.MAX_VALUE;
        int direction = -1;
        for(int i = 0; i < nums.length; ++i){
            for(int j = i+1, k = nums.length-1; j < k;){
                int sum = nums[i] + nums[j] + nums[k];
                if(target == sum) return sum;
                else if(target > sum){
                    if(target-sum < closest){
                        closest = target-sum;
                        direction = -1;
                    }
                    ++j;
                }else {
                    if(sum-target < closest){
                        closest = sum-target;
                        direction = 1;
                    }
                    --k;
                }
            }
        }
        return target + direction*closest;
    }
}

思路解析

本题的解法和leetcode 15. 三数之和（Java版的三种解法）中的解法二总体来说是一模一样的。
我们需要理解的就是，有序数组的双指针算法，不仅能找到和等于给定值的两个数（如果存在的话），而且也能找到和最接近给定值的两个数。
有序数组的双指针算法只涉及前指针后移和后指针前移，直至两指针相遇，时间复杂度为 ，并没有穷举所有的两数和情况，那么会不会有漏掉的情况，即为什么可以前指针仅后移后指针仅前移呢？
下面给一个具体的实例，好理解一点：

例子
此时将 i 指针左移的话肯定不合理，因为指向 1 和 8 的情况已经比较过了。
例子
此时如果将 i 指针左移，通过比较的传递性可以发现这种情况其实也已经比较过了，因为当 i 指向 1，j 指向 8 时，已经小于 target 了（否则 i 不会后移），如果此时再指向 1 和 6，那就比之前指向 1 和 8 时更小于 target 了，肯定不会是最接近 target 的情况，可以排除掉。所以 i 指针一直后移即可，同理 j 指针一直前移即可。