16. 3Sum Closest-M

16. 最接近的三数之和-M

label: 数组，三数之和，双指针，将三数改为两数

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

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

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

分析：
有了《15 三数之和》的经验，这道题就简单多了，同样的思路，先排序，外层一个遍历循环，取left=i+1,right=size-1,比较sum和target,调整left、right位置，即可将三个数转化为两个数据，这样整体下来O(N ^ 2)。

先排序，后将三个数转化为两个数：

/* 执行用时 :12 ms, 在所有 Go 提交中击败了95.24%的用户 内存消耗 :2.7 MB, 在所有 Go 提交中击败了25.81%的用户 */
package main
import ("fmt""sort"
)
type slice []int
func (s slice)Len()int{
    return len(s)
}
func (s slice)Less(i,j int)bool{
    return s[i]<s[j]
}
func (s slice)Swap(i,j int){
    s[i],s[j]=s[j],s[i]
}
func abs(a int)int{
    if a<0{
    return -a}else{
    return a}
}
//O(N^2),先排序，将三个数转化为两个数
func threeSumClosest(nums []int, target int) int {
    sort.Sort(slice(nums))min:=nums[0]+nums[1]+nums[2]for i:=0;i<len(nums);i++{
    left,right:=i+1,len(nums)-1//sum<target,left++;sum>target,right--,这样O(N^2),便可处理完for left < right{
    sum:=nums[i]+nums[left]+nums[right]if sum>target{
    right-=1}else if sum<target{
    left+=1}else{
    return sum}if abs(min-target)>abs(sum-target){
    min=sum}}}return min
}
func main() {
    tables:=[][]int{
    {
    1,-1,2,1,-4},}for _,t:=range tables{
    fmt.Println(threeSumClosest(t[1:],t[0]))}
}