two-sumsV3-hashtable.cpp (1146B)
1 /*Conceptual: 2 3 2 9 8 7 8 0 9 1 8 6 78 72 88 19 62 4 _ _ _ _ _ _ _ _ _ _ __ __ __ __ __ 5 [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14] 6 7 8 //Leet Ratings 9 // Speed Memory 10 //Total 4ms 11.3MB 11 //Beats 99.3% 13.46% 12 // 13 //This is so fast because it uses an O(n) algorithm where it only goes through 14 //the entire vector one time at most by utilizing a hashmap that stores 15 //values and the index that they occured at for faster execution at the 16 //cost of memory. 17 18 19 20 */ 21 22 23 #include <iostream> 24 #include <vector> 25 #include <map> 26 27 using namespace std; 28 29 vector<int> twoSum(vector<int>& nums, int target) { 30 map<int, int> vals_map; 31 int second_val; 32 int first_val; 33 for(int i = 0 ; i < nums.size(); ++i){ 34 int diff = target - nums[i]; 35 if(vals_map.count(diff)){ 36 second_val = vals_map.find(diff)->second; 37 first_val = i; 38 break; 39 } 40 vals_map.insert( pair<int, int> (nums[i] , i)); 41 } 42 return {first_val, second_val}; 43 } 44 45 int main(){ 46 vector<int> input = {0 , 3, 1}; 47 vector<int> new_vec = twoSum(input , 4); 48 cout << new_vec[0] << " " << new_vec[1] << endl; 49 return 0; 50 }