2.5　最接近的三数之和

题目描述（第16题）

给定一个包括n个整数的数组nums和一个目标值target。找出nums中的3个整数，使它们的和与target最接近。返回这3个数的和。假定每组输入只存在唯一答案。

例如，给定数组nums=[-1,2,1,-4]和target=1。

与target最接近的3个数的和为2，即-1+2+1=2。

思路

和上面三数之和的题目描述几乎一样，唯一不同的是，这次数组中的3个数相加可能永远达不到target，这里要返回三数相加最接近target的和，从数学角度说就是三数之和与target的差的绝对值最小。

和上面的思路一样，仍然先进行排序，然后固定1个元素，内部循环使用双指针即可。唯一不同的是判断逻辑有所不同，不再是三数之和等于target，而是三数之和与target的差的绝对值最小。由于题目要求返回3个数之和，因此用一个变量res去记录3个数相加的和，如果该和与target的差的绝对值更小，就去更新res。

代码

复杂度分析

●　时间复杂度：和三数之和一样，时间复杂度为O(n2)。

●　空间复杂度：不确定，取决于内部排序算法的具体实现。

n数和问题是力扣（LeetCode）比较经典的系列题目之一，我们从最经典的两数之和、三数之和、四数之和开始，到最接近的三数之和，以及四数之和II，不难发现它们有着很强的关联性。希望读者从这些题目中可以找到规律和“套路”，不管是思路上、解法上，还是代码模板上。