3Sum Closest

@(算法)[算法, Two Pointers, Sort, Array]

这一题怎样用一句话描述？

找出数组中三个不同的数字之和最接近给定值的组合

用到什么算法？什么数据结构？

首先应该想到最暴力的解法，否则就是基本功不扎实了，所以O(n^3)的算法一定要会写

然后面试官肯能会问了，有没有办法优化呢？例如，优化成O(n^2)，这里是有方法的。也许我们第一个想到的会是动态规划，首先动归是用来找最优解的，契合这里的找最接近target的描述，不过动归主要是用来优化非线性时间的算法，假如暴力解已经是O(n^2)或者O(n^3)那么就不用考虑动归了。

这里的思路很简单，首先对数组排序，然后选定一个起点，再通过两个指针不断夹逼，举个例子：

给定数组和target

S = {-1 2 1 -4}, target = 1

首先对S排序后得到

S = {-4 -1 1 2}

这个时候，我们选定－4为起点，两个指针分别指向剩余数组的首尾，即-1和2，考虑目前的和是

-4 + -1 + 2 = -3 < target

所以，可以把左边的指针向右移，这样计算出来的sum值会比刚才打；反之则可以将右边的指针向左移，直至两个指针相遇，这样便可以不断逼近target。注意，起点的选择只能在i = 0 ~ n - 2之间，不包含n - 2，因为还要腾出两个位置放两个指针。

这一题便是两个指针(Two Pointers)的经典应用！

通过这题学到了什么？

掌握暴力解的基础上，学会最优解！基础为先，进阶次之，一步一个脚印才能不断进步

可能(已经)遇到的BUG有？

下意识得认为这一题是一个组合问题，于是使用了Subsets的模板，结果导致算法超时。因为这一题根本不需要得出所有的子集合，最暴利的方法也只是得出所有长度为3的子集就行了。当然Subsets的模板也很重要，要背下来！