16. 最接近的三数之和

题目

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

难度：🌟🌟🌟

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0
 
提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -10⁴ <= target <= 10⁴

题解

看到最逼近三数之和，首先想到的是通过遍历把三数相加的所有情况全部全部算出来，然后和 target 比较差值，取最接近的三数之和。

func threeSumClosest1(nums []int, target int) int {
	n := len(nums)
	if n == 3 {
		return sum(nums[0], nums[1], nums[2])
	}
	s := sum(nums[0], nums[1], nums[2])
	delta := abs(s - target)
	for i := 0; i < n-2; i++ {
		for j := i + 1; j < n-1; j++ {
			for k := j + 1; k < n; k++ {
				s1 := sum(nums[i], nums[j], nums[k])
				if abs(s1-target) < delta {
					s = s1
					delta = abs(s1 - target)
				}
			}
		}
	}
	return s
}

但这样时间复杂度是 O(n³)，在 LeetCode 中执行超时。
因此我们需要想办法降低时间复杂度。
新的思路是：可以先对数组进行排序，然后固定一个数，再去 nums[start....] 中寻找最接近 target-delta 的两数之和。

代码实现

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func sum(a, b, c int) int {
	return a + b + c
}

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	n := len(nums)
	closestSum := sum(nums[0], nums[1], nums[2])
	if n == 3 {
		return closestSum
	}
	for i := 0; i < n-2; i++ {
		left, right := i+1, n-1
		for left < right {
			threeSum := sum(nums[i], nums[left], nums[right])
			if abs(threeSum-target) < abs(closestSum-target) {
				closestSum = threeSum
			}
			if threeSum > target {
				// 缩小右侧搜索范围
				right--
			} else if threeSum < target {
				left++
			} else {
				return threeSum
			}
		}
	}
	return closestSum
}