Why my O(N^2) solution with unordered_set lead to time limit exceeded?


  • 0
    O

    vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> triplests;
    unordered_set<string> tt;
    for (int i = 0; i < nums.size(); i++) {
    unordered_set<int> numSet;
    for (int j = i + 1; j < nums.size(); j++) {
    auto it = numSet.find(0 - nums[i] - nums[j]);
    if (it != numSet.end()) {
    string key = to_string(nums[i])+ to_string(*it)+to_string(nums[j]);
    if(tt.find(key)==tt.end()) {
    triplests.push_back(vector<int>{nums[i], *it, nums[j]});
    tt.insert(key);
    }
    }
    numSet.insert(nums[j]);
    }
    }
    return triplests;


  • 0
    O

    i think this solution is O(N^2). Am i wrong?


  • 0
    A

    I had the same issue (in Java), but when I add the following optimisation:

    if (nums[i] > 0) {
    break;
    }

    I got accepted


  • 0
    O

    @avokin thanks. I have tried your solution but it seems doesn't work. I guess maybe the time limit of c++ is stricter than java.But I have solved this problem by using two point... Anyhow ,thanks for your reply.


Log in to reply
 

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