LeetCode16-最接近的三数之和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/3sum-closest/

中文链接：https://leetcode-cn.com/problems/3sum-closest/

题目详述

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

1
2
3
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题目详解

本题可以用三重循环的暴力方法解决这个问题，不过复杂度比较高。类似于 LeetCode15-三数之和 这道题，可以运用数双指针的思想，不断地进行扫描更新，将时间复杂度降为 O(n^2)。

  • 首先把数组从小到大进行排序。
  • 遍历过程中固定一个元素。
  • 再运用双指针的思想，一个从左往右扫描，一个从右往左扫描，扫描过程中不断更新。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class LeetCode_00016 {

    public int threeSumClosest(int[] nums, int target) {
        // 首先从小到大排序
        Arrays.sort(nums);
        int n = nums.length;
        // 初始化为任意一个可能值
        int res = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n; ++i) {
            int l = i + 1;
            int r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                int diff = sum - target;
                // 如果相等直接返回，不可能有更接近的
                if (diff == 0) {
                    return sum;
                }
                // 更接近就更新
                if (Math.abs(diff) < Math.abs(res - target)) {
                    res = sum;
                }
                if (diff > 0) { // 因为数组有序，说明右侧的数过大，所以下标左移
                    --r;
                } else {        // 因为数组有序，说明左侧的数过小，所以下标右移
                    ++l;
                }
            }
        }
        return res;
    }
}