TLE for a O(n^2) algorithm


  • 0
    V
    vector<vector<int> > threeSum(vector<int> &num) {
        vector < vector < int > > result;
        int size = num.size();
        if(size < 3){
            return result;
        }
        sort(num.begin(), num.end());
        int temp;
        vector < int > tempResult;
        for(int i = 0; i < size - 2; i ++){
            if(i != 0 && num[i] == num[i - 1]){
                continue;
            }
            if(num[i] > 0){
                break;
            }
            int j = i + 1, k = size - 1;
            while(j < k){
                if(- num[i] - num[j] < num[j]){
                    break;
                }
                temp = num[i] + num[j] + num[k];
                if(temp == 0){
                    tempResult = {num[i], num[j], num[k]};
                    result.push_back(tempResult);
                }else{
                    if(temp > 0){
                        do{
                            k --;
                        }while(num[k] == num[k + 1]);
                    }else{
                        do{
                            j ++;
                        }while(num[j] == num[j - 1]);
                    }
                }
            }
        }
        return result;
    }

  • 0
    S

    Could you please detail your post? Explain your O(N^2) algorithm and add comments in your code.


  • 0
    C

    what is TLE stand for? I can see it everywhere, kinda curious


  • 0

    TLE means "Time Limit Exceeded".


  • 0

    This has nothing to do with whether you algorithm is O(N^2). The reason it TLE is because there is a bug in your code.


Log in to reply
 

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