Two Sum
Find pair of two numbers with sum given exists in array return indexes
1)Nested loop check all pairs TC o(n²).
2)Two pointers approach TC o(nlogn)+o(n).
3)HashMap TC o(n) SC o(n) .
3 Approach: Most efficient one
Get suhama’s stories in your inbox
Join Medium for free to get updates from this writer.
Using Hashmap is the most efficient approach to solve problem find pair of number which sum equals to target value we have to return their indexes
Lets first revise these concepts
Vector a dynamic array in C+++ that can grow in size.Complement difference between target and current number.Unordered map a data structure that have collection of key value pairs
#include <unordered_map>
#include <vector> // using libraries
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> num_map; // Create a map to store numbers and their indices
for (int i = 0; i < nums.size(); i++) {
int complement = target — nums[i]; // Calculate the complement
// Check if the complement exists in the map
if (num_map.find(complement) != num_map.end()) {
return {num_map[complement], i}; // Return the indices of the complement and the current number
}
// Store the current number and its index in the map
num_map[nums[i]] = i; // Store the current number with its index
}
return {}; // Return an empty vector if no solution is found
}
};
Suhama Mustafa
