Hope you all are safe and making best use of Your Quarantine Period to enhance your skills. In this Post, we will cover the solution for 2 sum problem. We will cover the full solution in C++ language.
Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.
Explanation:
In this problem, we are given an array of integers and we have to return the indices of the pair that add up to a specific number given to us.
INPUT:
[2,7,11,15]
9
OUTPUT:[0,1]
As the sum of integers at 0 and 1 index(2 and 7) gives us a sum of 9.
INPUT:
[3,7,9,10,5]
8
OUTPUT:[0,4]
A simple method is to use a two nested loop and generate all the pairs and check for their sum. This method will have a time complexity of O(N^2) but the problem should be solved in a linear time limit.
The Efficient Approach is to use hashing. We will use a hash map and while iterating, we will check for each element y, if there exists a target-y in the map. If it exists, we will return the indices of both integers. Otherwise, We will store that element and it’s index as key and mapped value in the map. This is done to further check for that element and also get it’s index if required.
Let us look at a example for better understanding:
Array = [3,4,8,6,7]
Target = 9
Steps:
Create a hash map and start iterating through the Array.
Check for first element 3, since no value is associated with (9-3=)6 in the map so insert (3,0) in the map.
Check for 4 , since no value is associated with 5 so insert (4,1) in the map.
Check for 8, since no value is associated with 1 so insert (8,2) in the map.
Check for 6, this time a value associated with 3 exist so return the index of 6 and value associated with 3 which is the index of integer 3.
Output: [0, 3]
Note: We are using map to link integer with index as it given the same element does not appear twice.
Let's see the full solution to this problem:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> m;
vector<int> v;
for(int i=0;i<nums.size();i++)
{
if(m.find(target-nums[i])!=m.end())
{
v.push_back(m[target-nums[i]]);
v.push_back(i);
return v;
}
m[nums[i]]=i;
}
return v;
}
};
THANKS FOR READING!
If you have any doubt, please let us know by posting in comments.