A C++ solution, not the best, but easy to understand.


  • 1
    L
    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
            vector<vector<int> > retVec; 
            if (num.size()<3) return retVec;
            std::sort(num.begin(), num.end());
            
            for(int i=0; i<num.size()-2;i++) {
                if(num[i]>0) break;
                for(int j=i+1; j<num.size()-1;j++) {
                    if(num[i] + num[j] >0) break;
                    for(int k=j+1; k<num.size(); k++) {
                        if(num[i] + num[j] + num[k] == 0) {
                            vector<int> newVec;
                            newVec.push_back(num[i]);
                            newVec.push_back(num[j]);
                            newVec.push_back(num[k]);
                            std::sort(newVec.begin(), newVec.end());
                            retVec.push_back(newVec);
                        } else if (num[i] + num[j] + num[k] > 0)
                            break;
                        while (k<num.size()-1 && num[k+1] == num[k]) k++;
                    }
                    while (j<num.size()-2 && num[j+1] == num[j]) j++;
                }
                while (i<num.size()-3 &&  num[i+1] == num[i]) i++;
            }
            return retVec;
        }
    };

  • -3
    R

    This is a O(n3) solution, which should fail.


  • 0
    N

    Thanks! This is easy to understand and just the one I am seeking for.


Log in to reply
 

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