Why this program will lead to time limited exceeded about question 3sum


  • 0
    D

    class Solution{
    public:
    vector<vector<int>> threeSum(vector<int> &num) {
    vector<vector<int>> result;

        if (num.size() < 3) return result;
        sort(num.begin(), num.end());
        const int target = 0;
    
        auto last = num.end();
        for (auto a = num.begin(); a < prev(last, 2); ++a) {
            auto b = next(a);
            auto c = prev(last);
            while (b < c) {
                if (*a + *b + *c < target){
                    b++;
                 }else if (*a + *b + *c > target){
                    c--;
                }else{
                    result.push_back({*a, *b, *c});
                    b++;
                    c--;
                }
            }
        }
        sort(result.begin(),result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        
        return result;
    }
    

    };


  • 0
    T

    Why shouldn't it? Test cases have changed. Longer test data with duplicates added.


  • 0
    L

    He means this program is just O(n^2), why lead to time limited also.


Log in to reply
 

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