16. 最接近的三数之和

难度: 中等

来源: 每日一题 2023.07.10

---

给你一个长度为 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

class Solution {
    public int threeSumClosest(int[] nums, int target) {

    }
}

分析与题解

---

• 排序 + 双指针

  这个题目和昨天的三数之和的解法基本一致.

  整体的解题思路是这样的.

  

  • 首先使用Java的API Arrays.sort 对数组进行排序.

    Arrays.sort(nums); // 排序
    

  • 排序完成之后,我们需要进行一次遍历,在遍历中寻找到第一个基准点,如上图所示.

  • 然后就是定义左右指针进行查看, 这里还是要注意这题有一个特殊点就是 左指针的起始位为 i + 1 , 如图所示.

  • 紧接着,就需要判断 三者之和与 target 的差值与原来的差值进行比较,如果满足条件则进行替换.

    int value = nums[i] + nums[left] + nums[right];
    if (Math.abs(target - absMinValue) > Math.abs(target - value)) {
        absMinValue = value;
    }
    

  • 如果三者之和为 target 直接返回. 如果不是,则就是对左右指针正常移动即可.

    if (value == target) {
        return value;
    } else if (value < target) {
        left++;
    } else if (target < value) {
        right--;
    }
    

  最终,整个解题过程如下所示.

  class Solution {
      public int threeSumClosest(int[] nums, int target) {
          Arrays.sort(nums);
          int length = nums.length;
          int absMinValue = Integer.MAX_VALUE;
          for (int i = 0; i < length; i++) {
              int left = i + 1;
              int right = length - 1;
              while(left < right) {
                  int value = nums[i] + nums[left] + nums[right];
                  if (Math.abs(target - absMinValue) > Math.abs(target - value)) {
                      absMinValue = value;
                  }
                  if (value == target) {
                      return value;
                  } else if (value < target) {
                      left++;
                  } else if (target < value) {
                      right--;
                  }
              }
          }
          return absMinValue;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n²)
  • 空间复杂度: O(㏒n)

  结果如下所示.