16.最接近的三数之和

题目描述

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

示例1:

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

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

思路

1.与三数之和类似，先将数组升序排序，然后从左到右固定一个数字，从右侧的两边开始检索答案，类似于快速排序的首位指针。
2.当三数和大于target时，将右指针左移；小于时左指针右移；等于时直接返回target。

Java代码实现

   public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        //防止target为负数时，溢出。
        long ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length-2; i++) {
            int left = i+1;
            int right = nums.length-1;
            while(left<right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == target)
                    return 0;
                else if(sum < target)
                    left++;
                else if(sum > target)
                    right--;
                if(Math.abs(ans-target)>Math.abs(sum-target))
                    ans = sum;
            }
        }
        return (int) ans;
    }