描述 Description

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

For example, given array S = {-1 2 1 -4}, and target = 1.

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

[3Sum Closest]

分析 Analysis

题目有个限制就是只有唯一的结果，所以，如果发现完全相等的，也就可以停下来了。

参考3SUM，算法基本一样。但是因为是找最接近的，所以要考虑所有情况，left循环到length-2

    for (int left = 0; left < nums.length-2; left++)

然后还是mid和right分别从两端往中央扫描，如果mid+right还比较小，那就需要mid右移，反之right左移（每次如果有最小的就存下来）。

代码 Code

int threeSumClosest(vector<int> &num, int target) {        
    vector<int> v(num.begin(), num.end()); // I didn't wanted to disturb original array.
    int n = 0;
    int ans = 0;
    int sum;

    sort(v.begin(), v.end());

    // If less then 3 elements then return their sum
    while (v.size() <= 3)
        return accumulate(v.begin(), v.end(), 0);

    n = v.size();

    ans = v[0] + v[1] + v[2];
    for (int i = 0; i < n-2; i++) {
        int j = i + 1;
        int k = n - 1;
        while (j < k) {
            sum = v[i] + v[j] + v[k];
            if (abs(target - ans) > abs(target - sum)) {
                ans = sum;
                if (ans == target) return ans;
            }
            (sum > target) ? k-- : j++;
        }
    }
    return ans;
}