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)
java:
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
int len = num.length;
List<List<Integer>> list = new LinkedList<List<Integer>>();
if(len<3){
return list;
}
Arrays.sort(num);
int i=0;
while(i<len-2){
int s=i+1;
int e=len-1;
while(s<e){
if(num[s]+num[e]==0-num[i]){
List<Integer> lst = new LinkedList<Integer>();
lst.add(num[i]);
lst.add(num[s]);
lst.add(num[e]);
list.add(lst);
while(s+1<len&&num[s+1]==num[s]){
s++;
}
s++;
while(e-1>=0&&num[e-1]==num[e]){
e--;
}
e--;
}else if(num[s]+num[e]<0-num[i]){
s++;
}else{
e--;
}
}
while(i+1<len&&num[i+1]==num[i]){
i++;
}
i++;
}
return list;
}
}
c++:
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > r;
int n=num.size();
sort(num.begin(),num.end());
if(n<3)
return r;
int i=0;
while(i<n-2){
int k1 = num[i];
int s = i+1,e=n-1;
while(s<e){
if(num[s]+num[e]==0-k1){
vector<int> v;
v.push_back(k1);
v.push_back(num[s]);
v.push_back(num[e]);
r.push_back(v);
while(s+1<=n-1&&num[s]==num[s+1]){
s++;
}
s++;
while(e-1>=i&&num[e]==num[e-1]){
e--;
}
e--;
}else if(num[s]+num[e]<0-k1){
s++;
}else{
e--;
}
}
while(i+1<=n-1&&num[i]==num[i+1]){
i++;
}
i++;
}
return r;
}
};