leetcode: 几个数之和系列

两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
unordered_map<int, int> m;
vector<int> res;
for (int i=0;i<len;i++) {
if (m.find(target - nums[i]) != m.end()) {
res.push_back(i);
res.push_back(m[target - nums[i]]);
return res;
}
m[nums[i]] = i;
}
return res;
}
};

三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
vector<vector<int>> res;
if (len < 3)
return res;
sort(nums.begin(), nums.end());
for(int i=0;i<len-2;i++) {
if(nums[i]>0) break;
if(i>0 && nums[i]==nums[i-1])
continue;
int l=i+1;
int r=len-1;
while(l<r) {
int sum = nums[i]+nums[l]+nums[r];
if(sum == 0) {
res.push_back(vector({nums[i], nums[l], nums[r]}));
while(l<r && nums[l] == nums[l+1])
l++;
while(l<r && nums[r] == nums[r-1])
r--;
l++;
r--;
} else if(sum > 0)
r--;
else
l++;
}
}
return res;
}
};

最接近的三数之和

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

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

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
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int len = nums.size();
if(len < 3)
return target;
sort(nums.begin(), nums.end());
int m=nums[0]+nums[1]+nums[2];
for(int i=0;i<len-2;i++) {
int l=i+1;
int r=len-1;
while(l<r) {
int sum = nums[i]+nums[l]+nums[r];
if(abs(sum-target)<abs(m-target))
m = sum;
else if(sum>target)
r--;
else if(sum<target)
l++;
else
return target;
}
}
return m;
}
};

思考与总结

两个数之和在考虑时间复杂度时,需要一次遍历时把结果算出来,所以考虑使用hash表查询的方式,遍历的时候同时保存,以时间来换取空间。
三个数求和时,其实可以考虑成两个数求和的普遍情况,两个数求和是三个数求和的特例,所以思路是一样的,难点在于去重,这里使用排序后更好去重,同时利用双指针双边递进快速找到目标值。
最接近这个题,其实和三者之和那个题差不太多,找到最小值时再替换掉最小值,如果最小值为0了,就直接可以退出了。
这三个题的难度依次递增,重点难点在于,hash_map使用、双指针、排序去重等思路,把这些思路作为知识点,多加巩固练习,用得多就自然会了,不用的东西,总有一天会忘记的。

nephen wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!