LeetCode 016 最接近的三数之和

双指针问题

问题

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

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

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

解答

关于三个数的和问题，我们可以参考两数之和问题。

首先将数组排序，达到非递减序；
之后遍历i ， 范围0 ~ len-2，作为三数中的第一个数；
取j = i + 1，其范围在1 ~ len-1中，作为第二个数，是从数组前端往后的指针；
取k = len - 1，其范围为len-1 ~ j，为第三个数，是从数组后端往前的指针；
当三个数相加后，其和若大于target，则k--前移；若小于target，则j++后移;若相等，则亦符合本题的最近和。
在遍历求和过程中，不断将当前sum与最近sum相比较，并根据判断做相应操作。

代码如下：

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        Arrays.sort(nums);
        int closestSum = 0;
        int diff = Integer.MAX_VALUE;

        for(int i = 0; i < len - 2; i++) {
            int left = i + 1;
            int right = len - 1;
            while(left < right) {
                int temp_sum = nums[i] + nums[left] + nums[right];
                int temp_diff = Math.abs(temp_sum - target);
                if(temp_diff < diff) {
                    closestSum = temp_sum;
                    diff = temp_diff;
                }
                if(temp_sum < target)
                    left++;
                else if(temp_sum > target)
                    right--;
                else
                    return temp_sum;
            }
        }
        return closestSum;
    }
}