How could I avoid Time Limit Exceeded


  • 0
    U

    I really do not know what's wrong with it. For some cases, it just show me TLE. However, when I test these cases on my own computer, it can be very fast.(less than 1 second).

            set<vector<int>/*, vector_cmp*/> res;
            vector<vector<int> > R;
            if ( num.size() < 3 ) return R;
            for (int i = 0; i < num.size() - 2; i ++) {
                for (int j = i + 1; j < num.size() - 1; j ++) {
                    for (int k = j + 1; k < num.size(); k ++) {
                        int a, b, c;
                        if ( num[i] + num[j] + num[k] != 0 ) continue;
    //					cout << num[i] << ' ' << num[j] << ' ' << num[k] << endl;
                        if ( num[i] <= num[j] ) {
                            if ( num[i] <= num[k] ) {
                                a = num[i];
                                if ( num[j] <= num[k] ) {
                                    b = num[j];
                                    c = num[k];
                                } else {
                                    c = num[j];
    								b = num[k];
                                }
                            } else {
                                a = num[k];
                                b = num[i];
                                c = num[j];
                            }
                        } else { // num[j] < num[i]
                            if ( num[j] <= num[k] ) {
                                a = num[j];
                                if ( num[i] <= num[k] ) {
                                    b = num[i];
                                    c = num[k];
                                } else {
                                    b = num[k];
                                    c = num[i];
                                }
                            } else {
                                a = num[k];
                                b = num[j];
                                c = num[i];
                            }
                        }
                        vector<int> v = {a, b, c};
    //					cout << a << ", " << b << ", " << c << endl;
                        res.insert(v);
    					/*
    					cout << "============================" << endl;
    		for (set<vector<int>, vector_cmp>::iterator it = res.begin();
    				it != res.end(); it ++)
    			cout << (*it)[0] << ", " << (*it)[1] << ", " << (*it)[2] << endl;
    		*/
                    }
                }
            }
            R.insert(R.begin(), res.begin(), res.end());
    /*	
    		for (set<vector<int>, vector_cmp>::iterator it = res.begin();
    				it != res.end(); it ++)
    			cout << (*it)[0] << ", " << (*it)[1] << ", " << (*it)[2] << endl;
    			*/
    			
            return R;

  • 9
    W

    Because it's O(N^3) complexity, which is very inefficient. Evaluating the execution time is not as convincing as evaluating time complexity, since your computer may be relatively high-end, and the same code running on another low-end machine may require much more time.


Log in to reply
 

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