leetcode 16. 最接近的三数之和 解题思路

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

解题思路

第一时间没什么思路，首先想到了简单粗暴的N3遍历，然后在基础上进行了一定的优化变成N2。
首先对数据按大小排序，然后开始第一轮遍历，此时我们先选nums[i]为三数中的第一个数。
那么问题就简化成了如何计算最接近的两数之和,target变为了（target-nums[i]）,数据范围变成了（i+1到length-1）。
注意此时两数的取值的范围，由于数组已经排序，所以两数之和的最大值为nums[length-2]+nums[length-1],最小值为nums[i+1]+nums[i+2]。
这时需要一点小技巧，我们取数据两边的nums[i+1]和nums[length-1]分别记为j,k。然后将两数和与两数目标进行比较，两数和小于两数目标时，j后移一位，反之k前移一位，当j,k相遇时停止，i+1开始下一轮循环。过程中记下最接近目标值时的和，就是我们所需的值了。

public class SumOfThreeNum16 {
    public static void main(String[] args) {
        int[] test = { -1, 2, 1, -4 };
        System.out.println(threeSumClosest(test, 1));
    }

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int curTarget = 100000;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1, k = nums.length - 1; j < nums.length;) {
                if (j == k)
                    break;
                if (Math.abs(target - (nums[i] + nums[j] + nums[k])) < Math.abs(target - curTarget)) {
                    curTarget = nums[i] + nums[j] + nums[k];
                }
                if (target - (nums[i] + nums[j] + nums[k]) > 0) {
                    j++;
                } else if (target - (nums[i] + nums[j] + nums[k]) < 0) {
                    k--;
                } else {
                    return target;
                }

            }
        }
        return curTarget;
    }
}