题目描述
给你一个长度为 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
解法
方法一：排序 + 双指针
我们将数组排序，然后遍历数组，对于每个元素 $nums[i]$，我们使用指针 $j$ 和 $k$ 分别指向 $i+1$ 和 $n-1$，计算三数之和，如果三数之和等于 $target$，则直接返回 $target$，否则根据与 $target$ 的差值更新答案。如果三数之和大于 $target$，则将 $k$ 向左移动一位，否则将 $j$ 向右移动一位。
时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
ans = inf
for i, v in enumerate(nums):
j, k = i + 1, n - 1
while j < k:
t = v + nums[j] + nums[k]
if t == target:
return t
if abs(t - target) < abs(ans - target):
ans = t
if t > target:
k -= 1
else:
j += 1
return ans
|
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 | class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = 1 << 30;
int n = nums.length;
for (int i = 0; i < n; ++i) {
int j = i + 1, k = n - 1;
while (j < k) {
int t = nums[i] + nums[j] + nums[k];
if (t == target) {
return t;
}
if (Math.abs(t - target) < Math.abs(ans - target)) {
ans = t;
}
if (t > target) {
--k;
} else {
++j;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = 1 << 30;
int n = nums.size();
for (int i = 0; i < n; ++i) {
int j = i + 1, k = n - 1;
while (j < k) {
int t = nums[i] + nums[j] + nums[k];
if (t == target) return t;
if (abs(t - target) < abs(ans - target)) ans = t;
if (t > target)
--k;
else
++j;
}
}
return ans;
}
};
|
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 | func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
ans := 1 << 30
n := len(nums)
for i, v := range nums {
j, k := i+1, n-1
for j < k {
t := v + nums[j] + nums[k]
if t == target {
return t
}
if abs(t-target) < abs(ans-target) {
ans = t
}
if t > target {
k--
} else {
j++
}
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | function threeSumClosest(nums: number[], target: number): number {
nums.sort((a, b) => a - b);
let ans: number = 1 << 30;
const n = nums.length;
for (let i = 0; i < n; ++i) {
let j = i + 1;
let k = n - 1;
while (j < k) {
const t: number = nums[i] + nums[j] + nums[k];
if (t === target) {
return t;
}
if (Math.abs(t - target) < Math.abs(ans - target)) {
ans = t;
}
if (t > target) {
--k;
} else {
++j;
}
}
}
return ans;
}
|
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 | /**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function (nums, target) {
nums.sort((a, b) => a - b);
let ans = 1 << 30;
const n = nums.length;
for (let i = 0; i < n; ++i) {
let j = i + 1;
let k = n - 1;
while (j < k) {
const t = nums[i] + nums[j] + nums[k];
if (t === target) {
return t;
}
if (Math.abs(t - target) < Math.abs(ans - target)) {
ans = t;
}
if (t > target) {
--k;
} else {
++j;
}
}
}
return ans;
};
|
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 | class Solution {
/**
* @param int[] $nums
* @param int $target
* @return int
*/
function threeSumClosest($nums, $target) {
$n = count($nums);
$closestSum = $nums[0] + $nums[1] + $nums[2];
$minDiff = abs($closestSum - $target);
sort($nums);
for ($i = 0; $i < $n - 2; $i++) {
$left = $i + 1;
$right = $n - 1;
while ($left < $right) {
$sum = $nums[$i] + $nums[$left] + $nums[$right];
$diff = abs($sum - $target);
if ($diff < $minDiff) {
$minDiff = $diff;
$closestSum = $sum;
} elseif ($sum < $target) {
$left++;
} elseif ($sum > $target) {
$right--;
} else {
return $sum;
}
}
}
return $closestSum;
}
}
|