Simple idea to speed up the look-up using c++


  • 5
    W

    The idea is very simple, but very effective in speeding up the code to `beat' more than 99% of the submissions. By adding the condition elem.first < value - elem.first, it avoids checking whether a pair of values twice compared with the condition elem.first != value - elem.first.
    For example, if target = 3, and we have added 1 and 3 in the hash table. Then we don't need to check 3, because if 3 can be a candidate for the pair summing up to 3, then we should be able to check 0 instead.
    This can save roughly half of the time when no pairs exist for the target.

    class TwoSum {
    public:
    	void add(int number) {
    	    elemCount[number]++;
    	}
    
    	bool find(int value) {
    	    for (auto elem : elemCount) {
    	        if ( (elem.first< value-elem.first && elemCount.count(value - elem.first))||
    	        (elem.first == value - elem.first && elem.second > 1)) {
    	            return true;
    	        }
    	    }
    	    return false;
    	}
    private:
        unordered_map<int, int> elemCount;
    };

Log in to reply
 

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