C++ O(n^2) solution but with remove duplicated items TIME LIMITED EXCEEDED!! why?


  • 0
    Z
    vector<vector<int> > threeSum3(vector<int> &num)
    {//O(n^2)
        DWORD t1,t2,t3;
        t1 = GetTickCount();
        sort(num.begin(),num.end());
        vector<vector<int> > triple;
        for(int i=0;i<num.size();i++)
        {
            int thrid = num[i];
            int s = i+1;
            int e = num.size()-1;
            while(s<e)
            {
                vector<int> temp;
                if(num[s]+num[e] ==  -thrid)
                {
                    temp.push_back(thrid);
                    temp.push_back(num[s]);
                    temp.push_back(num[e]);
                    triple.push_back(temp);
                    s++;
                    e--;
                }
                else if(num[s]+num[e] <  -thrid)
                    s++;
                else
                    e--;
            }
        }
        t2 = GetTickCount();
        cout << "second before" << t2-t1 << endl;
        for(int i = triple.size()-1;i>=0;i--)
            for(int j = i-1;j>=0;j--)
        {
            if(triple[i][0] == triple[j][0] &&
                triple[i][1] == triple[j][2] &&
                triple[i][2] == triple[j][2] )
                {
                    triple.pop_back();
                    i--;//
                }
    
    
        }
        t3 = GetTickCount();
        cout << "second" << t3-t2 << endl;
        cout << "second all" << t3-t1 << endl;
        return triple;
    }
    

    In the above code , WHY am i got the time limited exceeded???
    my code is just the same as :
    https://oj.leetcode.com/discuss/10756/my-accepted-o-n-2-solution-without-hashmap


  • 0
    X

    before

    if(i > 0 && num[i] == num[i - 1])
     continue;   
    int third = num[i]

Log in to reply
 

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