题目描述
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Constraints:
- 3 <= nums.length <= 10^3
- -10^3 <= nums[i] <= 10^3
- -10^4 <= target <= 10^4
题目分析
这个问题就是3sum问题的一个简单变换，我们依然使用解决3sum问题的思路来解决即可
- 首先对
nums数组排序 - 倒序遍历nums
- 对于nums[i]，利用双指针探测i之前的元素是否满足条件
[-4, -1, 1, 2]
↑ ↑ ↑
l r i
当 nums[l] + nums[r] + nums[r] < target时，由于nums是升序排列的，那么将l右移一位，继续探测下一个可能的值
反之亦然
示例代码
func threeSumClosest(nums []int, target int) int {
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
mindiff := math.MaxInt32
sum := 0
for i := len(nums) - 1; i >= 2; i-- {
l, r := 0, i-1
for l < r {
// 如果刚好相等，直接return即可
if nums[l]+nums[r]+nums[i] == target {
return target
}
// 如果差值小于当前记录的最小差值，更新sum与mindiff
if abs(target-nums[l]-nums[r]-nums[i]) < mindiff {
sum = nums[l] + nums[r] + nums[i]
mindiff = abs(target - nums[l] - nums[r] - nums[i])
}
// 如果3者相加小于target，左指针右移
if nums[l]+nums[r]+nums[i] < target {
l++
} else {
// 否则右指针左移
r--
}
}
}
return sum
}
func abs(a int) int {
if a < 0 {
return -1 * a
}
return a
}