O(n^2) solution. Beats 78.30%


  • 0
    N
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int> >vv;
            map<string,int>mp;
            if(nums.size()<3)return vv;
            vector<int>v;
            int i,j,k=nums.size();
            sort(nums.begin(),nums.end());
            for(i=0;i<k-2;i++)
            {
                if(i!=0)
                {
                    while(nums[i-1]==nums[i])i++;
                }
                int l=i+1,r=nums.size()-1;
                while(l<r)
                {
                    if(nums[i]+nums[l]+nums[r]==0)
                    {
                        v.push_back(nums[i]);v.push_back(nums[l]);v.push_back(nums[r]);
                        vv.push_back(v);
                        v.clear();
                        int templ=nums[l],tempr=nums[r];
                        while(nums[l]==templ&&l<r)
                        {
                            l++;
                        }
                        while(nums[r]==tempr&&l<r)
                        {
                            r--;
                        }
                    }
                    else if(nums[i]+nums[l]+nums[r]>0)
                    {
                        while(nums[i]+nums[l]+nums[r]>0&&l<r)r--;
                    }
                    else 
                    {
                        while(nums[i]+nums[l]+nums[r]<0&&l<r)l++;
                    }
                }
            }
            return vv;
        }
    };

Log in to reply
 

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