0016.md

16. 3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解法

在一个数组中，找到三个元素：nums[i]、nums[j]、nums[k]，要求它们的和值最接近于target，返回最后的和值。

“最接近target”就是要求与target差值的绝对值最小，使用一个变量记录每次3个元素的和，计算与target的差值，找到最小的那个。

在遍历元素，计算3个元素和的时候，怎么减少遍历过程中的计算？

1、可以使用三层的嵌套循环来求得所有3个元素组合的结果，时间复杂度是$O(N^3)$

2、在Q_0015的问题中，先对数组排序，然后使用两个指针，从前后同时遍历，并在遍历时跳过值相等的元素，时间复杂度$O(N^2)$

代码实现如下。

代码实现

public int threeSumClosest(int[] nums, int target) {
    // 对特殊情况的处理
    int result = 0;
    if (nums == null || nums.length == 0) {
        return result;
    }
    if (nums.length <= 3) {
        for (int num : nums) {
            result += num;
        }
        return result;
    }
	// 先给一个初始值
    result = nums[0] + nums[1] + nums[2];
    // 对数组排序
    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 1; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == target) {
                return sum;
            } else if (sum < target) {
                j++;
                while (j < k && nums[j] == nums[j - 1]) {
                    j++;
                }
            }else {
                k--;
                while (j < k && nums[k] == nums[k + 1]) {
                    k--;
                }
            }
            result = Math.abs(target - sum) > Math.abs(target - result) ? result : sum;
        }
    }
    return result;
}

在上面代码中，在更新 下标j、下标k时，既要根据 sum 值与 target 之间的大小关系，还要与前一个值（nums[j - 1]、nums[k + 1]）比较，直到与前一个值不相等。

总结

在一个数组中查找组合时，使用双指针可以减少嵌套循环的层数，对数组先排序，可以加快遍历的速度。