[数据结构与算法]LeetCode：最接近的三数之和

题目

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

审题

从一个数组中拿出三个数，使得这三个数的和与目标值的差值最小，这三个数具有唯一解的性质。
该题如果使用暴力破解法，时间复杂度为 O(n^3)，这是一个比较糟糕的破解方式。

思路

找出每个数组元素的另外两个最优解，使得这三个元素之和与目标值的差值达到最小。

为了能够把握数组三个元素之和与目标值的大小，从而找到比当前三个元素更加合适的元素值，我们可以先对数组进行一次有序排序，这样就可以准确把握三个元素之和与目标值的大小关系。

如果三数之和比目标值小，我们可以尝试往数组的右边找更大的元素来找寻更优解。
如果三数之和比目标值大，我们可以尝试往数组的左边找更小的元素来找寻更优解。

实现

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 首先对数组进行一次有序排序
        Arrays.sort(nums);
        int i, l, r, sum, n = nums.length;
        // 随便获取目标值和三位数的差绝对值
        int result = nums[0] + nums[1] + nums[2];
        int cha = Math.abs(target - result), temCha;
        // 循环的最后一位是 [n-3], 最后三位相加 [n-3] + [n-2] + [n-1]
        for (i = 0; i < n - 2; i++) {
            // 在循环过程中，如果当前循环的值和前一位值相等，就可以不用循环，因为值都是一样的，结果也就是一样的
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 获取当前循环的下一位元素
            l = i + 1;
            // 获取数组最后一位元素
            r = n - 1;
            while (l < r) {
                sum = nums[i] + nums[l] + nums[r];
                if (sum == target) {
                    return sum;
                }
                temCha = Math.abs(target - sum);
                // 如果差值更小，将差值更小的和赋值给 result，并保存更小的差值
                if (temCha < cha) {
                    result = sum;
                    cha = temCha;
                }
                // 因为是有序数组，如果值太小，则尝试增加左边的值
                if (sum < target) {
                    l++;
                }
                // 因为是有序数组，如果值太小，则尝试减小右边的值
                if (sum > target) {
                    r--;
                }
            }
        }
        return result;
    }
}

结果

解答成功:
执行耗时:4 ms,击败了97.88% 的Java用户
内存消耗:38 MB,击败了64.64% 的Java用户