lc.16.最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1 输出：0

提示：

3 <= nums.length <= 1000 -1000 <= nums[i] <= 1000 -104 <= target <= 104

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        if(n<=2) return 0;
        sort(nums.begin(),nums.end());

        int min_dist_is =  INT_MAX;
        int res = 0;
        for(int i=0;i<n;i++) {
            int a = nums[i];
            int l=i+1,r = n-1;
            while(l<r) {
                int b = nums[l],c = nums[r];
                int sum = a+b+c;
                if(sum>target) {
                    if(min_dist_is > abs(sum-target)) res = sum,min_dist_is = abs(sum-target);
                    --r;
                }else if(sum<target) {
                     if(min_dist_is > abs(sum-target)) res = sum,min_dist_is = abs(sum-target);
                    ++l;
                }else {
                    return target;
                }
            }
        }
        return res;
    }
};