16. 3Sum Closest 最近三数之和

题目链接
tag:

• Medium
• Two Pointers

question:
  Given an integer array nums of length n 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.

Example1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example2:

Input: nums = [0,0,0], target = 1
Output: 0

Constraints:

• -3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

思路：
  这道题让求最接近给定值的三数之和，是在之前那道 3Sum 的基础上又增加了些难度，那么这道题让返回这个最接近于给定值的值，即要保证当前三数和跟给定值之间的差的绝对值最小，所以需要定义一个变量 diff 用来记录差的绝对值，然后还是要先将数组排个序，然后开始遍历数组，思路跟那道三数之和很相似，都是先确定一个数，然后用两个指针 left 和 right 来滑动寻找另外两个数，每确定两个数，求出此三数之和，然后算和给定值的差的绝对值存在 newDiff 中，然后和 diff 比较并更新 diff 和结果 closest 即可，其实还可以稍稍进行一下优化，遍历时每次判断一下，当 nums[i]*3 > target 的时候，就可以直接比较 closest 和 nums[i] + nums[i+1] + nums[i+2] 的值，返回较小的那个，因为数组已经排过序了，后面的数字只会越来越大，就不必再往后比较了，代码如下：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        // 快排+双指针
        int closest = nums[0] + nums[1] + nums[2];
        sort(nums.begin(), nums.end());
        int diff = abs(target - closest);
        for (int i = 0; i < nums.size() - 2; ++i) {
            if (nums[i] * 3 > target) return min(closest, nums[i] + nums[i+1] + nums[i+2]);
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                int new_diff = abs(sum - target);
                if (new_diff < diff) {
                    diff = new_diff;
                    closest = sum;
                }
                if (sum < target) ++left;
                else --right;
            }
        }
        return closest;
    }
};

参考：http://www.cnblogs.com/grandyang/p/4481576.html