2019-08-22【LeekCode题库problem-16】

GitHub 地址：coffeeTu-code

LeekCode 地址：题库

Language：Golang

/*

@题目

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

@示例:

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

@题目大意

给定一个数组，要求在这个数组中找出 3 个数之和离 target 最近。

@解题思路

这一题的解法是用两个指针夹逼的方法。先对数组进行排序，i 从头开始往后面扫。这里同样需要注意数组中存在多个重复数字的问题。具体处理方法很多，可以用 map 计数去重。这里笔者简单的处理，i 在循环的时候和前一个数进行比较，如果相等，i 继续往后移，直到移到下一个和前一个数字不同的位置。j，k 两个指针开始一前一后夹逼。j 为 i 的下一个数字，k 为数组最后一个数字，由于经过排序，所以 k 的数字最大。j 往后移动，k 往前移动，逐渐夹逼出最接近 target 的值。

*/

func threeSumClosest(nums []int, target int) int {
    sum, res, diff := 0, 0, math.MaxInt32
    sort.Ints(nums)
    for i := 0; i < len(nums)-2; i++ {
        for j, k := i+1, len(nums)-1; j < k; {
            sum = nums[i] + nums[j] + nums[k]
            if sum == target {
                return target
            } else if sum > target {
                k--
                if sum-target < diff {
                    res, diff = sum, sum-target
                }
            } else {
                j++
                if target-sum < diff {
                    res, diff = sum, target-sum
                }
            }
        }
    }

    return res
}