题目描述
给你一个长度为 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- -104 <= target <= 104
解法一：排序 + 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
func abs(num int) int {
if num < 0 {
return -num
}
return num
}
func threeSumClosest(nums []int, target int) int {
n := len(nums)
sort.Ints(nums)
ans := math.MaxInt32
for i := 0; i < n-2; i++ {
sum := nums[i] + nums[i+1] + nums[i+2]
if sum > target {
if abs(sum-target) < abs(ans-target) {
return sum
}
break
}
if i == 0 || nums[i] != nums[i-1] {
left, right := i+1, n-1
if left == i+1 || nums[left] != nums[left-1] {
sum := nums[i] + nums[n-2] + nums[n-1]
if sum < target {
if abs(sum-target) < abs(ans-target) {
ans = sum
}
} else {
for left < right {
cur := nums[i] + nums[left] + nums[right]
if cur == target {
return target
} else {
if abs(cur-target) < abs(ans-target) {
ans = cur
}
if cur > target {
right--
} else {
left++
}
}
}
}
}
}
}
return ans
}
|
