16. 3Sum Closest

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).

---

此题和LeetCode 3Sum类似，不过是要求一个三元组的和和target最相近，而不是等于0。思路一样，先排序，然后首尾指针向target夹逼。对于每一个外层循环，记录下该循环得到的最小diff，然后在所有diff中取最小。在遍历的过程中如果发现diff=0，直接返回target。 完整代码如下：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> diff(n, INT_MAX);
        vector<int> sum(n);
        for (int i = 0; i < n; i++) {
            if (i == 0 || nums[i] > nums[i – 1]) {
                int s = i + 1, t = n – 1;
                while (s < t) {
                    int tmp_sum = nums[i] + nums[s] + nums[t];
                    if (abs(tmp_sum – target) < diff[i]) {
                        diff[i] = abs(tmp_sum – target);
                        sum[i] = tmp_sum;
                    }
                    if (tmp_sum < target)
                        s++;
                    else if (tmp_sum > target)
                        t–;
                    else {
                        return target;
                    }
                }
            }
        }
        int min_diff = INT_MAX, ans;
        for (int i = 0; i < n; i++) {
            if (diff[i] < min_diff) {
                min_diff = diff[i];
                ans = sum[i];
            }
        }
        return ans;
    }
};

本代码提交AC，用时12MS。

二刷：
上面的代码过于复杂，其实没必要存储diff和sum，因为最终只是求一个closest，在循环中就可以保存最小值，代码如下：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (n < 3)
            return accumulate(nums.begin(), nums.end(), 0);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1, k = n – 1; j < k;) {
                int sum = nums[i] + nums[j] + nums[k];
                if (abs(sum – target) < abs(ans – target))
                    ans = sum;
                if (sum == target)
                    return target;
                else if (sum < target)
                    ++j;
                else
                    –k;
            }
        }
        return ans;
    }
};

本代码提交AC，用时6MS。