这下真的得好好重头开始学算法了，基于《代码随想录》，今天周日的目标是完成哈希章节，并复习字符串章节和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题，具体可以参考代码随想录和我的刷题仓库。
爱发电
