Here, i’m trying to solve leetcode’s TwoSum problem in cpp.
To my understanding, the question is asking us to find a pair of numbers from the given array whose sum equals the target value.
class Solution {public: vector<int> twoSum(vector<int>& nums, int target) {
Approach 1: — Brute Force approach
int n = nums.size();
int i,j;
for(i=0; i<n-1; i++){
for(j = i+1; j<n; j++){
if(nums[i] + nums[j] == target){
return {i,j};
}
}
}
return {i,j};
}
};
according to leetcode :
Runtime: 509 ms, faster than 27.42% of C++ online submissions for Two Sum.
Memory Usage: 10.2 MB, less than 87.78% of C++ online submissions for Two Sum.
Approach 2: — Hashmap
unordered_map<int,int>hash;
vector <int> result;
int i;
for(i=0;i<nums.size();i++)
{
if(hash.find(target-nums[i])!=hash.end())
{
result.push_back(hash[target-nums[i]]); //
result.push_back(i); // push index
return result;
}
else
hash[nums[i]] = i;
}
return result;
}
};
The code is self explainatory:
For each and every element of an array it sees if the (target-element) is present in the hashmap.