每天一题LeetCode【第14天】

T16. 3Sum Closest【Medium】

题目

给一个有 n 个整数的数组 S，找到 S 中的三个数，使得这三个数的和最接近传入的target(目标数)。并返回这三个数的 sum(和)。你何以假设每个输入都有一个确切的解答。

举个例子，如果给出数组 S = [-1, 2, 1, -4],并且 target(目标数) = 1

最接近的 sum 是 2.（-1 + 2 + 1 = 2）

思路

具体可以看代码注释~

代码

代码取自 Top Solution，稍作注释

 public int threeSumClosest(int[] num, int target) {
        //初始一个result
        int result = num[0] + num[1] + num[num.length - 1];
        //给num排序
        Arrays.sort(num);
        for (int i = 0; i < num.length - 2; i++) {
            int start = i + 1, end = num.length - 1;
            //在while中num[i]是一定的，选出的是i时，i后面的数和i能组成的离target最近的sum
            while (start < end) {
                int sum = num[i] + num[start] + num[end];
                //sum>target要减小sum,因为排好序了，所以end--
                if (sum > target) {
                    end--;
                } else {       //sum<=target时同理
                    start++;
                }
                //若相差小，则更新result值
                if (Math.abs(sum - target) < Math.abs(result - target)) {
                    result = sum;
                }
            }
        }
        return result;
    }

补充

这题发现当从数组里面挑选数相加为一个目标数是时，可以用先把数组排序，从两边往里相加凑数这样的方法。

之前写的类似的解法：T15 3Sum