[0015] 三数之和
题目描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
题目解析
- 本题是一道搜索题，是[0001]两数之和的进阶，难度在于本题涉及到3个数字且需要去重。本题的解题方法与两数之和类似，有暴力枚举法，哈希表查找法，排序后双指针查找法。建议在学习[0001]两数之和后进行练习。
不确定性
- 题中没有给出容器内整数的数量范围，因此对于算法的时间复杂度有要求
- 可能出现多个重复数字，因而会产生多个重复的答案
方法一：暴力搜索法
分析
- 循环遍历nums容器，找到三数相加为0的情况
- 对于所有可能的答案进行去重
- 找出所有情况后去重会相对复杂，所以在查找时，分两种情况：
- 对于nums中不重复的三个数字相加，查看是否有满足和为0的三个数值
- 对于nums中重复的数字，再次查找
思路
- 使用map对nums中出现的数字的数量进行统计
- 使用sort函数对nums排序，然后利用unique函数对nums去重
- 对内部无重复的nums进行遍历，查看是否有满足和为0的三个数值
- 若存在重复的数值，则查看是否在nums中是否有另一个数值可以与两个重复数值相匹配
注意
- 若nums容器中的数字的数量小于3个，则本题无解
- 三个（或以上）相同的数相加为0，有且仅有{0,0,0}的组合
知识点
复杂度
代码
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
|
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if (nums.size() < 3){
return res;
}
map<int, int> m;
for (int i = 0; i < nums.size(); i++){
if (m.find(nums[i]) == m.end()){
m.insert(pair<int, int>(nums[i], 1));
}
else{
m[nums[i]]++;
}
}
sort(nums.begin(), nums.end());
vector<int>::iterator unique_end = unique(nums.begin(), nums.end());
nums.erase(unique_end, nums.end());
if (nums.size() >= 3){
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++){
for (int j = i + 1; j < nums.size() - 1; j++){
for (int k = j + 1; k < nums.size(); k++){
if (nums[i] + nums[j] + nums[k] == 0){
res.push_back({ nums[i], nums[j], nums[k] });
}
}
}
}
}
if (m[0] >= 3){
res.push_back({ 0, 0, 0 });
}
for (map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++){
if (iter->second > 1 && iter->first != 0){
int target = 2 * iter->first;
for (int i = 0; i < nums.size(); i++){
if (nums[i] + target == 0){
res.push_back({ iter->first, iter->first, nums[i] });
}
}
}
}
return res;
}
|
方法二：哈希表法
分析
- 通过遍历容器中nums[i]和nums[j]找到，查找-nums[i]-nums[j]
- 在遍历的同时，每次可以将nums[j]存入哈希表，由于hashset是根据key值进行存储的，因此相同的key不会插入到表内
思路
- 对容器进行排序，方便去重
- 二重遍历容器的nums[i]和nums[j]，并将nums[j]存入hashset中，若hashset中存在值为-nums[i]-nums[j]，则将三个数值保存
注意
- 以nums[i]和nums[j]分别作为三个数中的第一和第二个数需要对相同的数值进行去重
知识点
复杂度
代码
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
|
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> res;
if (nums.size() < 3){
return res;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (i != 0 && nums[i] == nums[i - 1]){
continue;
}
unordered_set<int> set;
for (int j = i + 1; j < nums.size(); j++)
{
if (set.find(-nums[i] - nums[j]) != set.end())
{
res.push_back({ nums[i], nums[j], -nums[i] - nums[j] });
while (j + 1 < nums.size() && nums[j] == nums[j + 1]){
j++;
}
}
set.insert(nums[j]);
}
}
return res;
}
|
方法三：双指针法
分析
- 定下nums[i]，然后使用j和k分别从首尾进行移动
- 判断nums[j]+nums[k]和目标值-nums[i]的大小关系，若前者大，则将k值减小，若前者小，则将j值增大
思路
- 对数组进行排序（双指针法的前提）
- 固定nums[i]，j从i+1，k从nums.size()-1从两边开始判断，直到j>=i时停止
- 根据nums[j]+nums[k]和目标值-nums[i]的大小关系，调整j和k的值
注意
知识点
复杂度
时间复杂度 O(n^2^)
空间复杂度 O(1)
代码
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
| vector<vector<int> > threeSum(vector<int> &nums)
{
vector<vector<int>> res;
if (nums.size() < 3)
return res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
int j = i + 1;
int k = nums.size() - 1;
if (i != 0 && nums[i] == nums[i - 1])
continue;
while (j < k)
{
if (nums[j] + nums[k] == -nums[i])
{
res.push_back({ nums[i], nums[j], nums[k] });
j++;
k--;
while (j < k && nums[j] == nums[j - 1]){
j++;
}
while (j < k && nums[k] == nums[k + 1]){
k--;
}
}
else if (nums[j] + nums[k] < -nums[i]){
j++;
}
else{
k--;
}
}
}
return res;
}
|
相关题目