【Leetcode】16.最接近的三数之和

16. 最接近的三数之和

题目

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

示例：

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

方法

本题与15.三数之和 非常相似。

可以使用暴力方法计算出数组中任意三个数的和，最后取离target最近的和即可。但这种方法的时间复杂度为$O(n^3)$。

我们采用和15.三数之和相同的思路，先固定住第一个数，再通过双指针法找后两个数。

具体算法流程如下：

  • 先对数组排序，时间复杂度为O(nlogn)
  • 从头到尾遍历数组，当遍历到数组中元素nums[i]时，用双指针L和R指向在nums[i]后面的数组两端，即L = i+1, R = nums.length - 1
  • 如果 nums[i] == nums[i-1]，则说明该数字重复，重复计算没有意义，所以应该跳过
  • 计算三个指针所指元素的和sum,判断sum与目标target的距离，如果二者距离更近则更新结果res。
  • 双指针移动：因为数组有序，因此如果sum < target，则L右移，如果sum > target，则R左移。否则sum=target，直接返回target。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int threeSumClosest(int[] nums, int target) {
    int minDif = Integer.MAX_VALUE;
    int res = nums[0] + nums[1] + nums[nums.length - 1];
    Arrays.sort(nums);
    for(int i = 0; i < nums.length; i++){
        if(i >= 1 && nums[i] == nums[i - 1])
            continue;
        int L = i + 1;
        int R = nums.length - 1;
        while(L < R){
            int sum = nums[i] + nums[L] + nums[R];
            if(Math.abs(target - sum) < Math.abs(target - res))
                res = sum;
            if(sum < target)
                L++;
            else if(sum > target)
                R--;
            else
                return target;
        }
    }
    return res;
}

时间复杂度：O(n^2) （数组中每一个元素都对应着一个双指针操作）
空间复杂度：O(1)