https://leetcode.com/problems/3sum/
题目：
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
方法一：
两层循环+二分查找，复杂度O(n^2 logn). 太慢了
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> res;
vector<vector<int>> output;
vector<int> sol;
sort(nums.begin(),nums.end()); //sort first
int i,j,k,t,x,n=nums.size();
for(i=;i<n;i++){
for(j=i+;j<n-;j++){
t=nums[i]+nums[j];
x=findSol(-t,nums,j+,n-);
if(x!=-){
sol.clear();
sol.push_back(nums[i]);
sol.push_back(nums[j]);
sol.push_back(nums[x]);
res.insert(sol);
}
}
}
set<vector<int>> :: iterator iter;
for(iter=res.begin();iter!=res.end();iter++){
output.push_back(*iter);
}
return output;
}
int findSol(int target,vector<int> nums,int begin,int end){
if(nums[begin]==target)
return begin;
if(nums[end]==target)
return end;
if(nums[begin]>target||nums[end]<target)
return -;
int mid;
while(begin<=end){
mid=(begin+end)/;
if(nums[mid]==target)
return mid;
else if(nums[mid]>target){
end=mid-;
}
else
begin=mid+;
}
return -;
}
};
方法二： 一层循环加two sum思想（https://leetcode.com/problems/two-sum/）,O(n^2).
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
int i,t,a,b,k,n=nums.size();
for(i=;i<n-;i++){
t=-nums[i];
a=i+;
b=n-;
while(a<b){
k=nums[a]+nums[b];
if(k<t){
a++;
}
else if(k>t){
b--;
}
else{
vector<int> sol(,);
sol[]=nums[i];
sol[]=nums[a];
sol[]=nums[b];
res.push_back(sol);
while (a < b && nums[a] == sol[])
a++;
while (a < b && nums[b] == sol[])
b--;
}
}
while (i + < nums.size() && nums[i + ] == nums[i])
i++;
}
//deduplicate, but it is so slow!
//sort(res.begin(), res.end());
//res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
};