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 sol…

LeetCode-3Sum

C++:
class Solution {
private:
    vector<vector<int>> ret;
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ret.clear();
        if(num.size()<3) return ret;
        sort(num.begin(),num.end());
        vector<int> cur(3);
        for(int i=0;i<num.size()-2;i++){
            int j=i+1;
            int k=num.size()-1;
            while(j<k){
                if(num[i]+num[j]+num[k]<0) j++;
                else if(num[i]+num[j]+num[k]>0) k--;
                else{
                    cur[0]=num[i];
                    cur[1]=num[j];
                    cur[2]=num[k];
                    ret.push_back(cur);
                    j++;
                    k--;
                }
            }
        }
        sort(ret.begin(),ret.end());
        ret.erase(unique(ret.begin(),ret.end()),ret.end());
        return ret;
    }
};
Java:
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> ret=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> cur=new ArrayList<Integer>();
        if(num.length<3) return ret;
        Arrays.sort(num);
        for(int i=0;i<num.length-1;i++){
            int j=i+1;
            int k=num.length-1;
            while(j<k){
                if(num[i]+num[j]+num[k]<0) j++;
                else if(num[i]+num[j]+num[k]>0) k--;
                else{
                    cur.add(num[i]);
                    cur.add(num[j]);
                    cur.add(num[k]);
                    if(!ret.contains(cur)){ 
                        ArrayList<Integer> temp=new ArrayList<Integer>();
                        for(Integer it:cur) temp.add(it);
                        ret.add(temp);
                    } 
                    cur.clear();   
                    j++;
                    k--;
                }
            }
        }
        return ret;
    }
}