Two Sum Algorithm
The Two Sum Algorithm is a widely popular problem-solving approach in computer programming and data structures, which aims to find a pair of numbers within an array or list that add up to a given target sum. The algorithm is often used as a fundamental exercise to test one's understanding of language syntax, data structures (such as arrays, lists, or hash tables), and problem-solving techniques. It has various applications in real-life scenarios, ranging from e-commerce transactions, financial analysis to machine learning, and artificial intelligence.
The algorithm can be implemented using different techniques, such as brute-force, sorting, or hash maps. The brute-force approach involves iterating through each element in the array and checking if there exists another element that, when added to the current element, results in the target sum. This method, however, is not optimal as it has a time complexity of O(n^2). A more efficient approach involves sorting the array first, and then using a two-pointer technique where one pointer starts at the beginning and the other at the end of the array, moving inward until the target sum is found or the pointers meet. This approach has a time complexity of O(n log n). An even more efficient method is to use a hash map to store the complement of each number in the array (target sum minus the number) along with its index. By iterating through the array, if the number is found in the hash map, the indices of the two numbers that add up to the target sum are returned. This approach has a time complexity of O(n) and is widely considered the optimal solution for the Two Sum problem.
bool lessthan(const pair<int, int>& lhs, const pair<int, int>& rhs) {
if (lhs.first == rhs.first)
return lhs.second < rhs.second;
return lhs.first < rhs.first;
}
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<pair<int, int>> vnum;
for (size_t i = 0; i < numbers.size(); i++) {
vnum.push_back(make_pair(numbers[i], i + 1));
}
sort(vnum.begin(), vnum.end(), lessthan);
vector<int> ans;
int s = 0, e = vnum.size() - 1;
while (s < e) {
if (vnum[s].first + vnum[e].first == target) {
ans.push_back(min(vnum[s].second, vnum[e].second));
ans.push_back(max(vnum[s].second, vnum[e].second));
break;
}
else if (vnum[s].first + vnum[e].first > target)
e -= 1;
else
s += 1;
}
return ans;
}
};
