3Sum

//O(n^2)
vector<vector<int> > threeSum(vector<int> &num) {
    vector<vector<int> > ret;
    if(num.size()<3)
        return ret;
    sort(num.begin(),num.end());
    for (int i=0;i<num.size()-2&&num[i]<=0;i++)
    {
        // remove duplicates 
        if(i>0&&num[i]==num[i-1])
            continue;
        int start=i+1;
        int end=num.size()-1;
        while(start<end)
        {
            int sum=num[i]+num[start]+num[end];
            if(sum<0)
            {
                start++;
            }
            else if(sum>0)
            {
                end--;
            }
            else
            {
                vector<int> temp;
                temp.push_back(num[i]);temp.push_back(num[start]);temp.push_back(num[end]);
                ret.push_back(temp);
                // move the left pointer to right and skip duplicates; 
                do{start++;}while(start<end&&num[start]==num[start-1]);
                do{end--;}while(start<end&&num[end]==num[end+1]);
            }

        }
    }
    return ret;
}