TLE C++ O(n) add O(1) find, any suggestions?


  • 0
    D

    the following C++ program works on my computer, however got TLE when running on OJ, any suggestion how to improve?

    class TwoSum {
    public:
    
        // Add the number to an internal data structure.
    	void add(int number) {
    	    if(s.count(number)) sum.insert(number + number); //not first time add, only need to make sure number + number is added
    	    else {                                                  //first time
    	        for(auto& i : s) {
    	            sum.insert(i + number);
    	        }
    	        s.insert(number);
    	    }
    	    
    	}
    
        // Find if there exists any pair of numbers which sum is equal to the value.
    	bool find(int value) {
    	    return sum.count(value);
    	}
    private:
        unordered_set<int> s;
        unordered_set<int> sum;
    };
    

  • 0
    U

    I tnink the time complex of count in unordered_set is O(n). and this cant past the time limit test.


Log in to reply
 

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