1. Two Sum
There are two different method. The first one is brute force enumeration. Enumerate all possible pairs until find the result. However, the algorithm has high time complexity, $O(n^2)$.
The second method is using hash table to accelerate the searching part. In C++, we use unordered_map data structure. After define the hash table hasht, we use data values as key and their positions as value. hasht.emplace() helps the program store the pairs efficiently. Then, hasht.find() can help the program find the corresponding value equal to “target - nums[i]”. Finally, storing their positions in the return vector and return it.
//C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> indices;
unordered_map<int, int> hasht;
for (int j=0; j<nums.size(); ++j) {
hasht.emplace(nums[j],j);
}
for (int i=0; i<nums.size(); ++i) {
auto iter = hasht.find(target-nums[i]);
if (iter != hasht.end()) { //Prevent searching out of range
if (iter->second != i) { //second is position of values
indices.push_back(i);
indices.push_back(iter->second);
break;
}
}
}
return indices;
}
};
