SHARE
TWEET

Untitled

bbescos Jan 24th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. // Run-time complexity O(n2)
  8. // Memory complexity O(n)
  9. vector<int> find_indexes(const vector<int>& nums, int sum) {
  10.    
  11.     unordered_map<int, int> hashmap;
  12.     unordered_map<int, int> hashmap_index;
  13.     vector<int> result;
  14.    
  15.     for (int i = 0; i < nums.size(); ++i) {
  16.         int current = nums[i];
  17.         for (auto item : hashmap) {
  18.             int complement = sum - current - item.first;
  19.             if (hashmap.count(complement) != 0) {
  20.                 if ((item.first == complement && item.second > 1) || item.first != complement) {
  21.                     result.push_back(i);
  22.                     result.push_back(hashmap_index[item.first]);
  23.                     result.push_back(hashmap_index[complement]);
  24.                     return result;
  25.                 }
  26.             }
  27.         }
  28.        
  29.         ++hashmap[current];
  30.         hashmap_index[current] = i;
  31.     }
  32.    
  33.     return result;
  34. }
  35.  
  36. // Run-time complexity O(n2)
  37. // Memory complexity O(n)
  38. vector<int> find_values(const vector<int>& nums, int sum) {
  39.    
  40.     unordered_map<int, int> hashmap;
  41.     vector<int> result;
  42.    
  43.     for (int num : nums) {
  44.         for (auto item : hashmap) {
  45.             int complement = sum - num - item.first;
  46.             if (hashmap.count(complement) != 0) {
  47.                 if ((item.first == complement && item.second > 1) || item.first != complement) {
  48.                     result.push_back(num);
  49.                     result.push_back(item.first);
  50.                     result.push_back(complement);
  51.                     return result;
  52.                 }
  53.             }
  54.         }
  55.        
  56.         ++hashmap[num];
  57.     }
  58.    
  59.     return result;
  60. }
  61.  
  62. void print_vector(const vector<int>& vec) {
  63.     for (int i = 0; i < vec.size(); ++i) {
  64.         std::cout << vec[i] << std::endl;
  65.     }
  66. }
  67.  
  68. int main()
  69. {
  70.     vector<int> v1 = {1 ,2 ,3 ,4 ,1 ,6};
  71.     int sum1 = 5;
  72.    
  73.     vector<int> v2 = {1 ,2 ,3 ,4 ,1 ,6, 1, 2, 4, 1, 2, 6, 7, 10};
  74.     int sum2 = 10;
  75.    
  76.     print_vector(v1);
  77.     std::cout << std::endl;
  78.     std::cout << sum1 << std::endl << "Values:" << std::endl;
  79.     print_vector(find_values(v1, sum1));
  80.     std::cout << "Indexes:" << std::endl;
  81.     print_vector(find_indexes(v1, sum1));
  82.     std:cout << "---------------" << std::endl;
  83.     print_vector(v2);
  84.     std::cout << std::endl;
  85.     std::cout << sum2 << std::endl << "Values:" << std::endl;
  86.     print_vector(find_values(v2, sum2));
  87.     std::cout << "Indexes:" << std::endl;
  88.     print_vector(find_indexes(v2, sum2));
  89.  
  90.     return 0;
  91. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top