刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/3sum-closest/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个长度为 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^4 <= target <= 10^4

思路

这道题先对还是比较简单的，最关键有两个思路

• 先排序。这个是时间优化最大的，没有排序，就无法很好的完成剪枝
• 双指针。如果还是三层循环，无论如何剪枝，也是在O(N^2)复杂度之上，所以需要敲掉一层循环。而在确定一个元素 + 已经排序的基础上，利用双指针双向移动寻找结果，就变成了一个很好的降低复杂度的方法

其他的没有什么可说的了，上代码吧

代码

func threeSumClosest(nums []int, target int) int {
    // 先排序，便于处理
	sort.Ints(nums)

	n := len(nums)
    // 两种特殊情况快速返回
	if nums[0]+nums[1]+nums[2] >= target {
		return nums[0] + nums[1] + nums[2]
	} else if nums[n-1]+nums[n-2]+nums[n-3] <= target {
		return nums[n-1] + nums[n-2] + nums[n-3]
	}

    // 赋个初始值。或者直接 10^4 + 1000*3
	res := nums[0] + nums[1] + nums[2]
	if abs(nums[n-1]+nums[n-2]+nums[n-3]-target) < res {
		res = nums[n-1] + nums[n-2] + nums[n-3]
	}

	// 再往右就没有左右指针位置了，所以只到 n-3
	for i := 0; i < n-2; i++ {
		// 相同元素可以跳过，所有情况会被之前的数字包含
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
        // 左右指针
		l, r := i+1, n-1
		for l < r {
			sum := nums[i] + nums[l] + nums[r]
            // 恰好相等是最优解，不用再找了
			if sum == target {
				return sum
			}
            // 看差值绝对值大小
			if abs(sum-target) < abs(res-target) {
				res = sum
			}
			if sum < target {
				l++
                // 跳过相同元素
				for l < r && nums[l] == nums[l-1] {
					l++
				}
			} else {
				r--
                // 跳过相同元素
				for l < r && nums[r] == nums[r+1] {
					r--
				}
			}
		}
	}
	return res
}

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