16.3Sum 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;

    }

}```

评论

暂无评论