Instantly share code, notes, and snippets.

# nishantmendiratta/two-sum.md

Created Oct 26, 2021
Leet > Two Sum
1. Brute force solution `twoSumExpensive`. Select every element and find the remainder after that iterate over the array to check if remainder exists in the remaining array or note.

2. Better solution using the Hash table. Iterate over all elements and check if the remainder is present in hash table or not if not set the number and it's index using `map[nums[i]] = i`

``````// https://leetcode.com/problems/two-sum/
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
vector<int> twoSumExpensive(vector<int>& nums, int target) {
vector<int> mp;
for (int i = 0; i < nums.size(); i++) {
int rem = target - nums[i];
for (int j = i+1; j < nums.size(); j++) {
if (nums[j] == rem)  {
mp.push_back(i);
mp.push_back(j);
return mp;
}
}
}
return mp;
}
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int, int> mapp;
for (int i = 0; i < nums.size(); i++) {
if (mapp.find(target - nums[i]) != mapp.end()) {
ans.push_back(mapp[target - nums[i]]);
ans.push_back(i);
return ans;
} else {
mapp[nums[i]] = i;
}
}
return ans;
}
};

int main() {
Solution *sl = new Solution();
// vector<int> nums = {2,7,11,15};
// int target = 9;
vector<int> nums = {3,2,4};
int target = 6;
vector<int> res;
res = sl->twoSum(nums, target);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}

return 0;
}
``````