15. 3Sum
Medium
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
] 题解： 三个数的和，思路就是求任意两个数的和x，然后O(n^2),再用O(1)的搜索搜索-x是否再数组内就可以了，O(1)搜索用哈希就行，或者用O(longn）的二分的方法也可以接收，我用的自带的find函数，最后也过了
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
multiset<int> left;
multiset<int> right;
set<vector<int>> ans;
int fl = ;
for(int i = ;i < nums.size(); i++){
if(nums[i] == ) fl++;
else if(nums[i]<) left.insert(nums[i]);
else if(nums[i]>) right.insert(nums[i]);
}
set<int>:: iterator lit;
set<int>:: iterator rit;
for(lit = left.begin(); lit!=left.end(); lit++){
rit = lit;
rit++;
for(; rit != left.end(); rit++){
int tt = (*lit)+(*rit);
if(right.find(-tt)!=right.end()){
vector<int> New;
New.push_back( (*lit));New.push_back( (*rit));New.push_back( -tt);
ans.insert(New);
}
}
}
for(rit = right.begin(); rit!=right.end(); rit++){
lit = rit;
lit++;
for(; lit != right.end(); lit++){
int tt = (*lit)+(*rit);
if(left.find(-tt)!=left.end()){
vector<int> New;
New.push_back( -tt);New.push_back( (*rit));New.push_back( (*lit));
ans.insert(New);
}
}
}
if(fl>=){
set<int>:: iterator it;
for(it = left.begin(); it!=left.end(); it++){
if(right.find(-(*it))!=right.end()){
vector<int> New;
New.push_back((*it));New.push_back();New.push_back(-(*it));
ans.insert(New);
}
}
}
if(fl>=){
vector<int> New;
New.push_back();New.push_back();New.push_back();
ans.insert(New);
}
vector<vector<int>> finalans;
set<vector<int>>:: iterator i;
for(i = ans.begin(); i!=ans.end(); i++){
vector<int> t = (*i);
finalans.push_back(t);
}
return finalans;
}
};