leetcode-16. 最接近的三数之和

题目

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

返回这三个数的和。

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

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

思路

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        // 先排序
        sort(nums.begin(), nums.end());

        // x + y + z = target, x+y = target-z, sum = target-z;
        // x + y = sum;
        int res = 0;
        int minv = INT_MAX; // 三数之和与target的差值的绝对值 的 最小值

        for (int a = 0; a < nums.size(); a ++)
        {
            // 先找第1个数z=nums[a]，然后转化问题为 求 x + y 接近 sum
            int sum = target - nums[a];

            int left = a+1, right = nums.size() - 1;

            while (left < right)
            {
                // 当前 三数和 与 target 差最小，就更新 minv 和 结果
                if (abs(nums[left] + nums[right] - sum) < minv)
                {
                    minv = abs(nums[left] + nums[right] - sum);
                    res = nums[a] + nums[left] + nums[right];
                }

                // x + y 尽可能和 sum 接近
                // 如果相等，直接返回 target
                if (nums[left] + nums[right] == sum)
                    return target;
                else if (nums[left] + nums[right] < sum) 
                    left++;
                else if (nums[left] + nums[right] > sum)
                    right--;               
            }
        }
        return res;
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。