This is my solution use with O(n^2) without the hash map


  • 0
    N

    first we find the all the two sum of K, so a+b+c=0 equals a+b=-c.
    then we will find all the some,

      class Solution {
        public:
            vector<int> twoSum(vector<int> &num,int k,int from)
            {
                int i=from;
                int j=num.size()-1;
                vector<int> ret;
                while(i<j)
                {
                    if(num[i]+num[j]<k)
                        i++;
                    else if(num[i]+num[j]>k)
                        j--;
                    else
                    {
                        ret.push_back(num[i]);
                        ret.push_back(num[j]);
                        int s=i;
                        while(i<j&&num[i]==num[s])
                            i++;
                    }
                }
                return ret;
            }
            vector<vector<int> > threeSum(vector<int> &num) {
                sort(num.begin(),num.end());
                int i=0;
                vector<vector<int> > ret;
                while(i<num.size()){
                    vector<int> two=twoSum(num,-num[i],i+1);
                    for(int j=0;j<two.size();j+=2)
                    {
                        vector<int> t(3);
                        t[0]=num[i];
                        t[1]=two[j];
                        t[2]=two[j+1];
                        ret.push_back(t);
                    }
                    int s=i;
                    while(i<num.size()&&num[i]==num[s])
                        i++;
                }
                return ret;
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.