Solution
So the brute force solution is pretty straightforward: we go through each pair of numbers and check if their sum equals to the target. The time complexity is .
The two solutions are less trivial, but with lower time complexity
//Solution 1: O(N log N) time complexity
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<pair<int,int>> num_idx;
for (int i = 0 ; i < numbers.size() ; ++i)
num_idx.push_back(pair<int,int>(numbers[i], i+1));
sort(num_idx.begin(), num_idx.end());
int begin = 0, end = num_idx.size()-1;
while(num_idx[begin].first + num_idx[end].first != target){
if (num_idx[begin].first + num_idx[end].first < target)
begin ++;
else
end --;
}
vector<int>index_vec;
index_vec.push_back(min(num_idx[begin].second, num_idx[end].second));
index_vec.push_back(max(num_idx[begin].second, num_idx[end].second));
return index_vec;
}
};
//Solution 2: O(N) average time complexity, using hash table
class Solution {
public:
vector<int> twoSum(vector<int> & numbers, int target) {
vector<int> index_vec;
unodered_map<int, int>position;
for (int i = 0; i < numbers.size(); ++ i){
if (position.find(target - numbers[i]) != position.end()){ \\find it
index_vec.push_back(position[target - numbers[i]]);
index_vec.push_back(i+1);
break;
}
else
position[numbers[i]] = i+1;
}
return index_vec;
}
};