乐趣区

163Sum-Closet

题目:

给定一个 nums 由_n 个_整数和一个整数组成的数组 target,找出三个整数 nums,使总和最接近 target。返回三个整数的和。您可以假设每个输入都只有一个解决方案。

例:

给定数组 nums = \[-1,2,1,-4\],target = 1。最接近目标的总和为 2。(-1 + 2 + 1 = 2)

思路: 排序, 固定第一个数, 在剩余的数组里双指针扫描, 加起来和减 target 的绝对值比初始值小则替换.


    public int threeSumClosest(int\[\] num, int target) {int result = num\[0\] + num\[1\] + num\[num.length - 1\];

        Arrays.sort(num);

        for (int i = 0; i < num.length - 2; i++) {

            int start = i + 1, end = num.length - 1;

            while (start < end) {int sum = num\[i\] + num\[start\] + num\[end\];

                if(sum==target) return sum;// 先判断 可以减少不必要的流程

                else if (sum > target) {end--;} else {start++;}

                if (Math.abs(sum - target) < Math.abs(result - target)) {result = sum;}

            }

        }

        return result;

    }

}```
退出移动版