16. 最接近的三数之和

原题链接:16. 最接近的三数之和

 

solution:

        本题和三数之和很相似,在计算最接近target的时候,需要考虑大于target和小于target两种情

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        pair<int, int> res(INT_MAX, INT_MAX);
        sort(nums.begin(),nums.end());  //排序

        for(int i = 0;i < n;i++) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;   //去重
            for(int j = i + 1,k = n - 1;j < k;j++) {
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                while(k - 1 > j && nums[i] + nums[j] + nums[k - 1] > target) k--;
                //计算一次大于target的数和一次小于target的数
                int sum = nums[i] + nums[j] + nums[k];
                res = min(res, make_pair(abs(target - sum), sum));
                if(k - 1 > j) {
                    sum = nums[i] + nums[j] + nums[k - 1];
                    res = min(res, make_pair(abs(target - sum), sum));
                }
            }
        }
        return res.second; 
    }
};