3Sum Closest

最接近3数之和

题目

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解析重点

1.根据题目我们需要知道最接近target的x+y+z。为了知道当我们移动元素的时候3数的和是增大还是减小，我们需要对数组进行排序。
2.当排完序，我们固定一个数y=a[0]，然后x初始固定为a[1],z=a[n].我们可以知道当x右移时，3数和会增大，当z左移时会减小。由此，我们可以使用两个循环得到我们想要
的结果，第一层控制y的循环，第二层控制x、z的循环。

java代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 排序
        Arrays.sort(nums);
        int closestNum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int l = i + 1, r = nums.length - 1;
            while (l < r){
                int threeSum = nums[l] + nums[r] + nums[i];
                if (Math.abs(threeSum - target) < Math.abs(closestNum - target)) {
                    closestNum = threeSum;
                }
                if (threeSum > target) {
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    r--;
                } else if (threeSum < target) {
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    l++;
                } else {
                    // 如果已经等于target的话, 肯定是最接近的
                    return target;
                }

            }

        }

        return closestNum;
    }
}