My 52ms c++ solution, O(n^2)time


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

Log in to reply
 

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