题目描述
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
题解
最容易想到的方法，肯定是三重循环，暴力求解，但是时间复杂度过高为[latex] O(n^3) [/latex]。 这里借鉴昨天三数之和那一题的解题思路，采用排序+双指针的方法来求解，同样a固定，然后首尾指针分别指向b与c，当a+b+c=target，则最优解就是target。若a+b+c>target，指向c的指针向左移动；若a+b+c<target，指向b的指针向右移动。当两指针相遇本次循环结束，然后更改a的位置，重复上述操作，直到找到最优解。 起初，天真的以为当sum(a+b+c)由大于target转为小于target或者由小于target转为大于target时，就能找到本次循环的最优解，就能跳出循环，后来提交才发现并不是，所以还是老老实实的判断吧。
错误代码
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int len = nums.size(), beg, end, sum, res;
bool posFlag = false, negFlag = false, flag = false;;
int posSum, negSum;
for(int i =0; i < len - 2; ++i){
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
beg = i + 1, end = len - 1;
posFlag = false, negFlag = false;
while(beg < end){
sum = nums[i] + nums[beg] + nums[end];
if(sum > target){
--end;
posFlag = true;
posSum = sum;
}
else if(sum < target){
++beg;
negFlag = true;
negSum = sum;
}
else{
res = target;
flag = true;
break;
}
if(posFlag && negFlag){
if(!flag){
flag = true;
res = posSum - target > target - negSum?negSum:posSum;
}
else{
int tmp = posSum - target > target - negSum?negSum:posSum;
res = abs(tmp - target) > abs(res - target)?res:tmp;
}
break;
}
}
if(flag && res == target){
break;
}
if(posFlag && !negFlag){
if(i + 2 < len){
if(!flag){
flag = true;
res = nums[i] + nums[i + 1] + nums[i + 2];
}
else{
int tmp = nums[i] + nums[i + 1] + nums[i + 2];
res = abs(tmp - target) > abs(res - target)?res:tmp;
}
}
}
else if(negFlag && !posFlag){
if(i + 2 < len){
if(!flag){
flag = true;
res = nums[i] + nums[len - 1] + nums[len - 2];
}
else{
int tmp = nums[i] + nums[len - 1] + nums[len - 2];
res = abs(tmp - target) > abs(res - target)?res:tmp;
}
}
}
if(flag && res == target){
break;
}
}
return res;
}
};
|
代码
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
| class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int len = nums.size(), beg, end, sum, res;
for(int i =0; i < len - 2; ++i){
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
if(i == 0){
res = nums[0] + nums[1] +nums[2];
}
beg = i + 1, end = len - 1;
while(beg < end){
sum = nums[i] + nums[beg] + nums[end];
if(abs(sum - target) < abs(res - target)){
res = sum;
}
if(sum > target){
--end;
}
else if(sum < target){
++beg;
}
else{
return res;
}
}
}
return res;
}
};
|
执行结果
