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:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Tags: Array, Two Pointers
题意是让你从数组中找出最接近 target 的三个数的和
该题和 3Sum 的思路基本一样,先对数组进行排序,然后遍历这个排序数组,用两个指针分别指向当前元素的下一个和数组尾部,判断三者的和与 target 的差值来移动两个指针,并更新其结果,当然,如果三者的和直接与 target 值相同,那么返回 target 结果即可。
func threeSumClosest(nums []int, target int) int {
ans := nums[0] + nums[1] + nums[len(nums)-1]
sort.Ints(nums)
for i := 0; i < len(nums)-2; i++ {
start, end := i+1, len(nums)-1
for start < end {
sum := nums[i] + nums[start] + nums[end]
if sum > target {
end--
} else {
start++
}
if Abs(sum-target) < Abs(ans-target) {
ans = sum
}
}
}
return ans
}
func Abs(x int) int {
if x > 0 {
return x
}
return -x
}
思路2 ```go
```
如果你同我一样热爱数据结构、算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:awesome-golang-algorithm