Why my code TLE? C++, O(n^2)


  • 0
    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
            vector<vector<int> > v;
            if(num.size()<3)
                return v;
            sort(num.begin(),num.end());
            for(int i=0;i<num.size()-3;i++)
            {
                int l=i+1,r=num.size()-1;
                while(l<r)
                {
                    if(num[i]+num[l]+num[r]==0)
                    {
                        vector<int> t;
                        t.push_back(num[i]);
                        t.push_back(num[l]);
                        t.push_back(num[r]);
                        v.push_back(t);
                    }
                    else if(num[i]+num[l]+num[r]>0)
                    {
                        r--;
                    }
                    else 
                        l++;
                }
            }
            vector<vector<int> >::iterator it=unique(v.begin(),v.end());
            v.erase(it,v.end());
            return v;
        }
    };

  • 1
    S

    In the inner while loop, you should also move the l and r pointers for the num[i]+num[l]+num[r]==0 case; otherwise your program will get stuck there.


  • 0

    You forget "--r" and "++l" in “while(l<r)” loop.

    And also unique() function will waste some time.

    If you know Chinese, you can refer to LeetCode --- 15. 3Sum

    I just jump the duplicate element.


Log in to reply
 

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