My solution using map which time complexity O(nlgn)


  • 0
    M
    vector<int> twoSum(vector<int> &numbers, int target) {
    vector<int> result;
    map<int, vector<int> > imap;
    int pos1 = 0;
    int pos2 = 0;
    for(unsigned int i = 0; i < numbers.size(); i++)
    {
    	vector<int> ivec;
    	ivec.push_back(i);
    	pair<map<int, vector<int> >::iterator, bool> ip = imap.insert(pair<int, vector<int> >(numbers[i],ivec));
    	if(!ip.second)
    	{
    		ip.first->second.push_back(i);
    	}
    }
    for(unsigned int i = 0; i < numbers.size(); i++)
    {
    	int temp = target - numbers[i];
    	map<int, vector<int> >::iterator it = imap.find(temp);
    	if(it != imap.end())
    	{
    		if(temp == numbers[i] && it->second.size() >= 2)
    		{
    			for(unsigned int j = 0; j < it->second.size(); j++)
    			{
    				result.push_back(it->second[j] + 1);
    			}
    			return result;
    		}
    		else if(it->first != numbers[i])
    		{
    			pos1 = i+1;
    			pos2 = it->second[0]+1;
    			result.push_back(pos1);
    			result.push_back(pos2);
    			return result;
    		}
    	}
    }
    return result;
    

    }


Log in to reply
 

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