3Sum Closest

16. 3Sum Closest

分析

暴力做法就是三重循环，每种答案枚举一遍，求一个最接近的值。

用双指针优化。先枚举位置i，对每一个位置j，找到一个最小的位置k使得 nums[i] + nums[j] + nums[k] >= target，这样可以得到大于等于target的最小值。并且，当k满足前述条件时，必然有 nums[i] + nums[j] + nums[k - 1] < target，也就可以得到小于target的最大值。每次更新下这两个值即可。

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        pair<int, int> res(INT_MAX, INT_MAX);
        for (int i = 0; i < nums.size(); i ++ )
            for (int j = i + 1, k = nums.size() - 1; j < k; j ++ ) {
                while (k - 1 > j && nums[i] + nums[j] + nums[k - 1] >= target) k -- ;
                int s = nums[i] + nums[j] + nums[k];
                res = min(res, make_pair(abs(s - target), s));
                if (k - 1 > j) {
                    s = nums[i] + nums[j] + nums[k - 1];
                    res = min(res, make_pair(target - s, s));
                }
            }
        return res.second;
    }
};