16. 最接近的三数之和

一、题目

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

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

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

二、解答

2.1方法一:排序+双指针法

public static int threeSumClosest(int[] nums, int target) {
        //数组大小小于3
        if (nums == null || nums.length < 3){
            throw new IllegalArgumentException("No two sum solution");
        }
        //排序
        Arrays.sort(nums);
        //记录最小差异
        int difValue = Integer.MAX_VALUE;
        //记录最小差异时的nums[i] + nums[l] + nums[r]
        int difSum = 0;

        int len = nums.length;
        for (int i = 0 ; i < len; i++) {
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int l = i + 1;
            int r = len - 1;
            while (l < r && r > 0) {
                int sum = nums[i] + nums[l] + nums[r];
                int difTarget = sum - target;

                if (difTarget == 0) {
                    return sum;
                }

                if (difTarget > 0){
                    if (difValue > difTarget){
                        difValue = difTarget;
                        difSum = sum;
                    }
                    r--;
                }

                if (difTarget < 0){
                    if (difValue > -difTarget){
                        difValue = -difTarget;
                        difSum = sum;
                    }
                    l++;
                }
            }
        }
        return difSum;
    }