59.最接近的三数之和

描述

给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，
返回这三个数的和。

注意事项

只需要返回三元组之和，无需返回三元组本身

样例

例如 S = [-1, 2, 1, -4] and target = 1. 和最接近 1 的三元组是 -1 + 2 + 1 = 2

挑战

O(n^2) 时间, O(1) 额外空间

注意

1. 如果需要返回三元组，就需要像三数之和一样定义函数，定义results，进行形参传递

2. 可以先排序，因为默认的排序算法是归并排序

思路
三数实际上就是两根指针再加上for循环

代码

public class Solution {
    /*
     * @param numbers: Give an array numbers of n integer
     * @param target: An integer
     * @return: return the sum of the three integers, the sum closest target.
     */
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return -1;
        }
        
        Arrays.sort(nums);
        // 初值
        int bestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int start = i + 1;
            int end = nums.length - 1;
            // sum值要放到while循环里,不然start和end改变时sum，不发生变化
            while (start < end) {
                int sum = nums[i] + nums[start] + nums[end];
                if (Math.abs(sum - target) < Math.abs(bestSum - target)) {
                    bestSum = sum;
                }
                if (sum < target) {
                    start++;
                // 此处如果写成 if (sum > target)，如果数组只有三个元素出现 sum == target 情况会卡住
                } else {
                    end--;
                }
            }
        }
        return bestSum;
    }
}