16. sum of the nearest three numbers

Original link :16. The closest sum of three

 

solution:

        This question is very similar to the sum of three numbers , In calculating the closest target When , Greater than target And less than target Two emotions

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());  // Sort 

        for(int i = 0;i < n;i++) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;   // duplicate removal 
            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--;
                // Calculate once greater than target The sum of the number of is less than target Number of numbers 
                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; 
    }
};