# O(n) c++ using hashtable 44ms solution

• ``````class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
int n = numbers.size();
unordered_map<int , int> mp;
vector<int> nums;
for(int i = 0 ; i < numbers.size() ; i++){
if(mp.find(target-numbers[i]) != mp.end()
&& i != mp[target-numbers[i]]){
nums.push_back(mp[target-numbers[i]]+1);
nums.push_back(i+1);
}else{
mp[numbers[i]] = i;
}
}
return nums;
}
};``````

• `````` class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> result;
vector<int> num = numbers;
int count = numbers.size();
if(numbers.empty()){
return result;
}//if
sort(numbers.begin(),numbers.end());
for(int i = 0,j = count-1;i < j;){
int sum = numbers[i] + numbers[j];
if(sum == target){
return FindIndex(num,numbers[i],numbers[j]);
}
else if(sum > target){
j--;
}
else{
i++;
}
}//for
return result;
}
private:
// Find index of num
vector<int> FindIndex(vector<int> &numbers,int num1,int num2){
int count = numbers.size();
vector<int> result;
int index1,index2;
bool flag1 = false,flag2 = false;
for(int i = 0;i < count;++i){
if(flag1 == false && numbers[i] == num1){
index1 = i+1;
flag1 = true;
}
else if(flag2 == false && numbers[i] == num2){
index2 = i+1;
flag2 = true;
}
}//for
// index1 < index2
if(index1 > index2){
int tmp = index1;
index1 = index2;
index2 = tmp;
}//if
result.push_back(index1);
result.push_back(index2);
return result;
}
};
``````

• map is binary search tree, unordered_map is hashtable

• This is actually O(nlog(n)) time complexity

• switch map 2 unordered_map will increase the performance a lot.
and the if statement in the loop, can just keep the first part. just my opinion

• another brilliant idea~~

• using unordered_map , time decreased to 25ms... Thanks for your suggestion guys..

• sort(numbers.begin(),numbers.end());
it makes the program O(nlogn)

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