# Accepted C++ O(n) Solution

• ``````vector<int> twoSum(vector<int> &numbers, int target)
{
//Key is the number and value is its index in the vector.
unordered_map<int, int> hash;
vector<int> result;
for (int i = 0; i < numbers.size(); i++) {
int numberToFind = target - numbers[i];

//if numberToFind is found in map, return them
if (hash.find(numberToFind) != hash.end()) {
//+1 because indices are NOT zero based
result.push_back(hash[numberToFind] + 1);
result.push_back(i + 1);
return result;
}

hash[numbers[i]] = i;
}
return result;
}``````

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• Thanks for Sharing.
As a newbie, I don't understand why do you put "hash[numbers[i]] = i" behind? Is there any sequence between i and hash[numberToFind]? Many thanks.

• because there may be duplicate number.
put behind,don't affect counting.
sorry,my English is poor.

• Neat and efficient. But I think your algorithm need a time of O(nlogn) cause you use std::map which is based on BR tree, isn't it?

• Not Exactly. unordered_map is not based on BR tree, instread ,its hash function is based on direct hash and it use link-address to deal with collision.Instead , the map and multi_map is using BR Tree.

• this is O(nlog(n)) right? because hash.find() takes O(log(n)).

• although the unsorted_map's find say it takes constant time, but actually it is not that good. I tried the hash solution, it takes 64 ms, while another solution with std::sort only takes 28 ms.

• This post is deleted!

• why don't need to relate the map hash to the vector numbers ?

• I got some error but figured it out, thanks

• The function of "hash[numbers[i]] = i; " is retating the hash map<int ,int> hash and vector<int> numbers

• This post is deleted!

• Average case: constant.
Worst case: linear in container size.

• Your answer seems O(n) but when I submitted your answer, the runtime was 20ms, which is worse than my answer of which the runtime is 16ms. My solution, However, is not O(n) but O(nlog(n)).

And I checked out the site:

http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

which shows that the complexity of find() is linear in worst case.

• I submitted a method using unordered_map takes 20ms, but when I using binary search and std::sort, It only takes 12ms. What is the worst case means in unordered map?

• Does your code take duplicate elements into consideration?
Input such as:

target = 8, items = [2 4 4 7 10]

• it has!
in your case , when it comes to the second '4', the first '4' is already int the map

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