leetcode 16.最接近的三数之和

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题解

首先对数组进行排序,计算出最小和最大的三数之和 min, max,如果 target > max 表明最接近的三数之和肯定就是 max,同理 target < min 时最接近的三数之和就是 min,当 targetmin, max 之间的时候,可以通过双指针判断最接近 target 的三数之和 sum,因为数组 nums 已经排好序了,所以可以通过判断 sum, target 的大小来移动左右指针 j, k

示例代码(go)

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
func threeSumClosest(nums []int, target int) int {
n := len(nums)
sort.Ints(nums)
min := nums[0] + nums[1] + nums[2]
max := nums[n-3] + nums[n-2] + nums[n-1]
if target > max {
return max
}
if target < min {
return min
}
res := min
for i := 0; i < n; i++ {
j, k := i+1, n-1
for j < k {
sum := nums[i] + nums[j] + nums[k]
if abs(target-sum) < abs(target-res) {
res = sum
}
if sum > target {
k--
} else if sum < target {
j++
} else {
return res
}
}
}
return res
}

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