距离上次更新本文已经过去了 208 天，文章部分内容可能已经过时，请注意甄别
这下真的得好好重头开始学算法了，基于《代码随想录》，今天周日的目标是完成哈希章节，并复习字符串章节和 KMP 算法。争取在四月中旬之前学完《代码随想录》里面的算法，欢迎大家监督我！
LetsOJ_多人刷题打卡：这是一个多人 OJ 打卡仓库
新建了一个 leetcode 的进度，OJ 刷题打卡仓库中的代码也重新归档。
注意：在手机上代码块中的下标位置会因为字体原因偏离，请使用电脑查看本博客。
问题
16. 最接近的三数之和 - 力扣（LeetCode）
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
1
2
3
4
5
6
7
8
| 示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
|
思路
这道题和 15 三数之和的思路很相似，15 题中要求是三数和为 0，这道题要求是和 target 越接近越好。其实就是在把目标值从 0 改成 target，并将三数和为 target 改成接近 target，中间会多一个记录差距数的操作。
使用排序 + 双指针来实现。排序后的数组已经有序，使用双指针的时候方便控制指针移动
- 如果和大于 target，则右侧指针–；
- 如果和小于 target，则左侧指针 ++；
这里还会涉及到一些优化，虽然题目中没有 15 题去重的要求，但跳过重复元素也能提高运行效率。
代码
最简单的方法
最简单的方式即不做任何去重，按照思路写代码就行。sum 大于或者等于 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
| class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int retNum = INT_MAX;
int retSum = 0;
sort(nums.begin(),nums.end());
for(int i = 0;i<nums.size();i++)
{
int left = i+1,right = nums.size()-1;
while(left < right)
{
int sum = nums[i] + nums[left] + nums[right];
int diff = abs(target-sum);
if(diff < retNum)
{
retNum = diff;
retSum = sum;
}
if(sum >= target){
right --;
}
else if(sum < target){
left++;
}
}
}
return retSum;
}
};
|
这样也能通过
下标 i 去重
下标 i 去重的目的是让 i 不处理刚刚已经处理过的值。注意，和 15 题 18 题中的去重都是相同的思路，要先处理完毕某个值再去重。
如下所示，假设我们需要对 -1 这个元素去重（不重复处理），应该先正常对第一个 -1 进行操作，再让 i 跳过第二个 -1 走到 2 的位置进行下一步操作
如果先去重，在三数之和中，假设 target=0，下面的情况就会被忽略。这里 i 已经走到了第二个 -1 的位置了，但 (-1) + (-1) +2 = 0 ，这种符合题意的结果就直接被跳过了。
1
2
3
|
if(nums[i] == nums[i+1])
continue;
|
如果我们不先执行去重，下标分布如下所示，右侧指针不断减，就能匹配上 -1 -1 2 这个三元组。
匹配上了之后再让 i 跳过第二个 -1 才是正确的。
1
2
3
|
if(i>0 && nums[i] == nums[i-1])
continue;
|
对于这道题，加上对 i 的去重后代码如下
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
| class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int retNum = INT_MAX;
int retSum = 0;
sort(nums.begin(),nums.end());
for(int i = 0;i<nums.size();i++)
{
if(i>0 && nums[i] == nums[i-1]){
continue;
}
int left = i+1,right = nums.size()-1;
while(left < right)
{
int sum = nums[i] + nums[left] + nums[right];
int diff = abs(target-sum);
if(diff < retNum)
{
retNum = diff;
retSum = sum;
}
if(sum >= target){
right --;
}
else if(sum < target){
left++;
}
}
}
return retSum;
}
};
|
left/right 去重
在 15 题三数之和的题解中会对 left 和 right 进行去重，同样是遵循先匹配再去重的操作。
假设当前指针位置如下，当前和为 5，假设小于 target，此时需要移动 left 指针
1
2
| -3 -1 -1 2 2 2 3 4
i l r
|
那么 left 指针移动的时候，可以直接移动到最后一个 2 的位置，因为对于求和而言它们没有任何区别。
1
2
| -3 -1 -1 2 2 2 3 4
i l r
|
代码如下
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
| class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int retNum = INT_MAX;
int retSum = 0;
sort(nums.begin(),nums.end());
for(int i = 0;i<nums.size();i++)
{
if(i>0 && nums[i] == nums[i-1]){
continue;
}
int left = i+1,right = nums.size()-1;
while(left < right)
{
int sum = nums[i] + nums[left] + nums[right];
if(sum == target){
return target;
}
int diff = abs(target-sum);
if(diff < retNum)
{
retNum = diff;
retSum = sum;
}
if(sum >= target){
while(left<right && nums[right] == nums[right-1]){
right--;
}
right--;
}
else if(sum < target){
while(left<right && nums[left] == nums[left+1]){
left++;
}
left++;
}
}
}
return retSum;
}
};
|
遇到 target 直接返回
如果三数和已经等于 target，可以直接返回，不需要继续执行。
The end
leetcode 和 16 题类似的有 15 题 / 18 题 / 454 题，具体可以参考代码随想录和我的刷题仓库。
爱发电
