乘风破浪：LeetCode真题_016

乘风破浪：LeetCode真题_016_3Sum Closest

一、前言

这一次，问题又升级了，寻找的是三个数之和最靠近的某个数，这是非常让人难以思考的，需要把三个数相加之后和最后给的目标进行比较，看看接近的程度，选择最接近的。不一定是等于目标。那么我们又该怎么做呢？？

二、3Sum Closest

2.1 问题

2.2 分析与解决

由上面的题意我们可以知道上一次的3sum所用的算法这边可能用不上了，需要进行改进。比如我们可以设想一个变量使得a+b+c≠target，但是a+b+c+temp=target，这样我们就能将这个问题化归到之前的3sum问题上，通过尽量缩小temp的大小来找到最佳的组合。但是问题是如何知道temp的范围呢[-oo,+oo]，但是绝对值越接近0越好。这样我们就陷入了一种死胡同而不能解决问题。我们可不可以想一下还是按照3sum的想法和方式来解答问题，首先从小到大排序，其次每次先选择一个元素，再选这个元素的下一个元素和最有一个元素对应的两个指针，来不断的遍历集合[start,end]，当我们求得的sum比target大了，我们就end--，反之则start++，每一次都计算此时的sum与target之差的绝对值和已经求得的差的绝对值的大小，如果更小则修改，直到所有的元素都遍历完毕，从而得到结果。

public class Solution {

    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) {

                    end--;

                } else {

                    start++;

                }

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

                    result = sum;

                }

            }

        }

        return result;

    }

}

三、总结

遇到问题我们要学会转变思维，不能在一棵树上吊死，一定要仔细的推敲一下，学会用收尾指针处理排序之后的数组的思维和能力，从而更快的完成问题。

巴特西

乘风破浪：LeetCode真题_016_3Sum Closest