16. 最接近的三数之和

难度中等838收藏分享切换为英文接收动态反馈
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

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

提示：

  • 3 <= nums.length <= 10^3
  • -10^3 <= nums[i] <= 10^3

  • -10^4 <= target <= 10^4

    1. int n = nums.size();
    2.   sort(nums.begin(), nums.end());
    3.   int mx = 1e7;
    4.   auto upda = [&](int curr)
    5.   {
    6.       if (abs(curr - target) < abs(mx - target))
    7.           mx = curr;
    8.   };
    10.   for (int first = 0; first < n-1; ++first)
    11.   {
    13.       if (first > 0 && nums[first] == nums[first - 1])
    14.           continue;
    15.       int second = first + 1, thr = n - 1;
    17.       while (second < thr)
    18.       {
    19.           int sum=nums[first] + nums[second] + nums[thr];
    20.           if (sum == target)
    21.               return target;
    22.           upda(sum);
    23.           if ((sum-target)<0)
    24.           {                
    25.               ++second;
    26.           }
    27.           else
    28.           {
    29.               --thr;
    30.           }
    31.           if (second == thr)
    32.               break;     
    33.       }
    34.   }
    35.   return mx;