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; 
    }
};