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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
int length = nums.size();
unordered_map<int,int> hm;
for(int i=0;i<length;i++){
int rest = target - nums[i];//if i = length-1, exclude end index--"length-1",pres has key--"rest" -- found
if(hm.find(rest) != hm.end()){
return {i,hm[rest]};
}
hm[nums[i]] = i;
}
/* two pass hash table */
// unordered_map<int,int> hm;
// int length = nums.size();
// for(int i=0;i<length;i++){
// hm[nums[i]] = i;
// }
// for(int i=0;i<length;i++){
// int rest = target-nums[i];
// if(hm.find(rest) != hm.end() && hm[rest] != i){
// return {i,hm[rest]};
// }
// }
/* Brutr Force */
// for(int i=0;i<length;i++){
// for(int j=i+1;j<length;j++){
// int sum = nums[i] + nums[j];
// if(sum == target){
// ret = {i,j};
// }
// }
// }
return {-1,-1};
}
};
