最接近的三数之和

LeetCode 16. 最接近的三数之和 (opens new window)

题目描述

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

示例

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

解题思路

如果采用三重循环暴力搜索每种3个数字的组合，那么时间复杂度达到O(n^3)。那么可以先对数组排序后固定第一个数再使用双指针法缩小后两个数的搜索范围，这样时间复杂度就降到了O(nlogn+n^2)=O(n^2)。 只不过需要注意的是最小距离是三数之和与target差的绝对值，而三个数的和是搜小搜索范围的指标，需要分开存储。

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int minDistance = Integer.MAX_VALUE, sum = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int left = i + 1, right = n - 1;
        while (left < right) {
            int tempDistance = Math.abs(target - nums[i] - nums[left] - nums[right]);
            if (tempDistance < minDistance) {
                minDistance = tempDistance;
                sum = nums[i] + nums[left] + nums[right];
            }

            if (minDistance == 0) {
                return sum;
            } else if (nums[i] + nums[left] + nums[right] > target) {
                right--;
            } else {
                left++;
            }
        }
    }
    return sum;
}