# O(n) is slower than O(nlogn)?

• the O(nlogn) solution ,beat 89.1%

O(nlogn)的解法，击败了89.1%的C++代码

`````` class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
vector<int> copy;
copy=nums;
sort(copy.begin(),copy.end());
auto fir=copy.begin();
auto sec=--copy.end();
while(fir<sec&&*fir+*sec!=target)
{
if(*fir+*sec>target)
sec--;
else
fir++;
}
auto pos1=nums.begin();
auto pos2=nums.begin();
if(*fir!=*sec)
{
pos1=find(nums.begin(),nums.end(),*fir);
pos2=find(nums.begin(),nums.end(),*sec);
if(pos1>pos2)
{
auto temp=pos1;
pos1=pos2;
pos2=temp;
}
}
else
{
pos1=find(nums.begin(),nums.end(),*fir);
pos2 = find(pos1+1, nums.end(), *sec);
}

result.push_back(pos1-nums.begin()+1);
result.push_back(pos2-nums.begin()+1);
return result;

}
};
``````

the O(n) solution ,only beat 58%

O（n）的解法，只击败了58%。

``````class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
auto pos1 = nums.begin();
auto pos2 = pos1;
unordered_map<int, vector<int>::iterator> iht;
auto pos = iht.begin();
for (auto i = nums.begin(); i != nums.end(); ++i)
{
pos = iht.find(target - *i);
if (pos == iht.end())
{
iht.insert(pair<int, vector<int>::iterator>(*i, i));
}
else
{
pos2 = i;
break;
}
}
pos1 = iht[target-*pos2];
result.push_back(pos1 - nums.begin() + 1);
result.push_back(pos2 - nums.begin() + 1);
return result;
}
};
``````

why? If you know ,please tell me.

为啥？跪求大神指教

• check the complexity of MAP

• for loop里有个find, Iht.find 本身就是O(n),所以下面其实是O(n)^2

• 用的是哈希表，哈希表查找是常数时间，即使不用哈希表，常规的MAP用红黑树实现的，查找也只要logN的时间，不会出现O（n2）

• This post is deleted!

• This post is deleted!

• 是我疏忽了 ，没细读，万分抱歉

• 这里用的并不是std::find，而是std::unordered_map::find, 二者不一样。你应该看http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

leetcode显示问题，下划线显示不出来。

• maybe try
iht.reserve(nums.size());
before the for loop

• How about {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,6} , find 11 ? When the given number set cause collision, worse case liner time O(n) comes. Also refer to "Complexity" session http://www.cplusplus.com/reference/unordered_map/unordered_map/insert/

• 很简单的问题，测试用例的关系啊，一共15个用例，长度也并不长，O(n)不一定比O(nlogn)花时间少啊，牵扯到系数和每步消耗时间啊。

• 我写for从两边查，有个用力10000多个元素的数组 说我超时。。。

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