My cpp code without hash map and costing O(n^2)


  • 5
    L
    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
            vector<vector<int> > result;
            if(num.size() <= 2){
                return result;
            }
            sort(num.begin(), num.end());
            for(int i = 0; i < num.size()-2; ++i){
                if(i > 0 && num[i] == num[i-1]){
                    continue;
                }
                int begin = i+1;
                int end = num.size()-1;
                while(begin < end){
                    int sum = num[i] + num[begin] + num[end];
                    if( sum == 0){
                        result.push_back({num[i], num[begin], num[end]});
                        begin++;
                        while(begin < num.size() && num[begin] == num[begin-1]){
                            begin++;
                        }
                        end--;
                        while(end >= 0 && num[end] == num[end+1]){
                            end--;
                        }
                    }else if(sum < 0){
                        begin++;
                    }else{
                        end--;
                    }
                }
            }
            return result;
        }
    };

Log in to reply
 

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