给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
思路:先对vector进行排序,这样的话如果前两个数之和大于9,那么也就可以直接pass了
然后把vector中的数依次放入map中,暴力循环,每次计算前两个数之和,再在map中找到第三个数,存在一个set中,再把set存在一个set中,避免重复。
在不重复的情况下把这三个数放入vector中。
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include <algorithm>
using namespace std;vector<vector<int>> threeSum(vector<int>& nums) {
map<int,int> temp;
vector<vector<int>> ans;
set<set<int>> anss;
int len = nums.size();
int n = ;
sort(nums.begin(), nums.end());
for (int i = ; i < len; i++)
{
temp[nums[i]] = i;
}
for (int i = ; i < len; i++){
for (int j = i+; j < len; j++)
{
int num = -nums[i] - nums[j];
if (num>) continue;
map<int, int> ::iterator add = temp.find(num);
if (add == temp.end() || add->second <= j) continue;
set<int> t;
t.insert(nums[i]);
t.insert(nums[j]);
t.insert(add->first);
//cout << nums[i] << nums[j] << add->first << endl;
if (anss.count(t) == )
{
anss.insert(t);
vector<int> t;
t.push_back(nums[i]);
t.push_back(nums[j]);
t.push_back(add->first);
ans.push_back(t);
cout << nums[i] << nums[j] << add->first << endl;
} }
}
return ans;
}int main(){
vector<int> a = { -, , , , -, - };
vector<vector<int>> ans = threeSum(a);
system("pause");
return ;
}