题目链接

题目描述

给定一个包括 n个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例

示例1：

输入：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

    思路

    排序+双指针

    本题与0015-三数之和类似，同样可以使用双指针。指针移动策略为：
    当和大于目标值时，移动右指针；当和小于目标时，移动左指针。同时可以跳过重复元素。
    另外，当和等于目标值时可以直接返回，因为没有比它更接近的了。

    题解

    1. class Solution {
    2.  public:
    3.   int threeSumClosest(vector<int>& nums, int target) {
    4.       int n = nums.size();
    5.       int minDiff = INT_MAX;
    6.       int ans = 0;
    8.       sort(nums.begin(), nums.end());
    9.       for (int i = 0; i < n; ++i) {
    10.           if (i > 0 && nums[i - 1] == nums[i]) {
    11.               continue;
    12.           }
    13.           int left = i + 1, right = n - 1;
    14.           while (left < right) {
    15.               int sum = nums[i] + nums[left] + nums[right];
    16.               if (sum == target) {
    17.                   return target;
    18.               }
    19.               int diff = abs(sum - target);
    20.               if (diff < minDiff) {
    21.                   ans = sum;
    22.                   minDiff = diff;
    23.               }
    24.               if (sum > target) {  //和太大，移动右指针
    25.                   --right;
    26.                   while (left < right && nums[right + 1] == nums[right]) {
    27.                       --right;
    28.                   }
    29.               } else if (sum < target) {
    30.                   ++left;
    31.                   while (left < right && nums[left - 1] == nums[left]) {
    32.                       ++left;
    33.                   }
    34.               }
    35.           }
    36.       }
    37.       return ans;
    38.   }
    39. };

    复杂度分析

  • 时间复杂度：0016-最接近的三数之和 - 图1，其中排序的复杂度为0016-最接近的三数之和 - 图2

  • 空间复杂度：0016-最接近的三数之和 - 图3，此为排序的空间复杂度，如果题目要求不能在原数组上修改，那么还需要保存副本，空间复杂度变为0016-最接近的三数之和 - 图4