两数之和
给定一个整数数组 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使用、双指针、排序去重等思路，把这些思路作为知识点，多加巩固练习，用得多就自然会了，不用的东西，总有一天会忘记的。