最接近的三数之和

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[ [-1, 0, 1], [-1, -1, 2] ]

02、题目分析

本题的暴力题解可以仿照二数之和，直接三层遍历，取和为0的三元组，并记录下来，最后再去重。但是作为一个有智慧的人，我们不能这么去做。

因为我们的目标是找数，当然使用指针的方式最简单。假若我们的数组为：

[-1, 0, 1, 2, -1, -4]

求解过程如下：首先我们先把数组排个序（原因一会儿说），排完序长这样：

因为我们要同时找三个数，所以采取固定一个数，同时用双指针来查找另外两个数的方式。所以初始化时，我们选择固定第一个元素（当然，这一轮走完了，这个蓝框框我们就要也往前移动），同时将下一个元素和末尾元素分别设上 left 和 right 指针。画出图来就是下面这个样子：

现在已经找到了三个数，当然是计算其三值是否满足三元组。但是这里因为我们已经排好了序，如果固定下来的数（上面蓝色框框）本身就大于 0，那三数之和必然无法等于 0。比如下面这种：

然后自然用脚指头也能想到，我们需要移动指针。现在我们的排序就发挥出用处了，如果和大于0，那就说明 right 的值太大，需要左移。如果和小于0，那就说明 left 的值太小，需要右移。(上面这个思考过程是本题的核心) 整个过程如下图所示：

其中：在第6行时，因为三数之和大于0，所以right进行了左移。最后一行，跳过了重复的-1。

然后啰嗦一句，因为我们需要处理重复值的情况。除了固定下来的i值（蓝框框），left 和 right 当然也是需要处理重复的情况，所以对于 left 和 left+1，以及 right 和 right-1，我们都单独做一下重复值的处理。（其实没啥处理，就是简单的跳过）

03、代码展示

四数之和其实与本题解法差不太多，把固定一个数变成两个，同样还是使用双指针进行求解就可以了。

Golang版本实现：

func threeSumClosest(nums []int, target int) int {
	if len(nums) == 3 {
		return nums[0] + nums[1] + nums[2]
	}
	sort.Ints(nums)
	sum := nums[0] + nums[1] + nums[2]

	for i := 0; i < len(nums); i++ {
		l := i+1
		r := len(nums) - 1
		for l < r {
			current := nums[i] + nums[l] + nums[r]
			if math.Abs(float64(sum - current)) > math.Abs(float64(target - current)) {
				sum = current
			}
			if current < target {
				l++
			} else if current == target {
				return target
			} else {
				r--
			}
		}
	}
	return sum
}