35 ms c++ solution. It can be improved by using Hashtable


  • 1
    I

    Same idea like using the hash table. Because my computer is using the old version c++, I used the multimap instead of unsorted_multimap. I think it can be improved by using the hash table.

    I have studied several solutions posted on the forum after I finished. Many buddy have started to find the result pair when they are looping the vector. This is a good habit, I think --- try to combine more things in short code. But using that way will import the complex judgement for each item. finally, the program will become a little slow.

    class Solution {
    public:
    	Solution()
    	{
    		temp.clear();
    	}
    
    	std::vector<int> twoSum(std::vector<int> &numbers, int target) {
    		int i = 1;
    		for(std::vector<int>::iterator it = numbers.begin(); it != numbers.end(); it++, i++)
    		{
    			temp.insert(std::pair<int, int>(*it, i));
    		}
    
    		int iIndex1 = 0, iIndex2 = 0;
    		while(temp.size() > 1)
    		{
    			int keyval = temp.begin()->first;
    			iIndex1 = temp.begin()->second;
    
    			temp.erase(temp.begin());
    			std::multimap<int, int>::iterator fIt = temp.find(target - keyval);
    			if(fIt != temp.end())
    			{
    				iIndex2 =  fIt->second;
    				break;
    			}
    		}
    
    		std::vector<int> rt;
    		if (iIndex1 < iIndex2)
    		{
    			rt.push_back(iIndex1);
    			rt.push_back(iIndex2);
    		}
    		else
    		{
    			rt.push_back(iIndex2);
    			rt.push_back(iIndex1);
    		}
    
    		return rt;
        }
    
    private:
    	std::multimap<int, int> temp;
    };

Log in to reply
 

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