SHARE
TWEET

Untitled

bbescos Jan 28th, 2019 72 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, vector<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) {
  21.                     result.push_back(i);
  22.                     result.push_back(hashmap_index[item.first][0]);
  23.                     result.push_back(hashmap_index[complement][0]);
  24.                     return result;
  25.                 }
  26.                 if (item.first == complement && item.second > 1) {
  27.                     result.push_back(i);
  28.                     result.push_back(hashmap_index[item.first][0]);
  29.                     result.push_back(hashmap_index[item.first][1]);
  30.                     return result;
  31.                 }
  32.             }
  33.         }
  34.         ++hashmap[current];
  35.         hashmap_index[current].push_back(i);
  36.     }
  37.     return result;
  38. }
  39.  
  40. // Run-time complexity O(n2)
  41. // Memory complexity O(n)
  42. vector<int> find_values(const vector<int>& nums, int sum) {
  43.    
  44.     unordered_map<int, int> hashmap;
  45.     vector<int> result;
  46.    
  47.     for (int num : nums) {
  48.         for (auto item : hashmap) {
  49.             int complement = sum - num - item.first;
  50.             if (hashmap.count(complement) != 0) {
  51.                 if ((item.first == complement && item.second > 1) || item.first != complement) {
  52.                     result.push_back(num);
  53.                     result.push_back(item.first);
  54.                     result.push_back(complement);
  55.                     return result;
  56.                 }
  57.             }
  58.         }
  59.        
  60.         ++hashmap[num];
  61.     }
  62.    
  63.     return result;
  64. }
  65.  
  66. void print_vector(const vector<int>& vec) {
  67.     for (int i = 0; i < vec.size(); ++i) {
  68.         std::cout << vec[i] << " ";
  69.     }
  70.     std::cout << std::endl;
  71. }
  72.  
  73. int main()
  74. {
  75.     vector<int> v1 = {1, 1, 1, 1};
  76.     int sum1 = 3;
  77.    
  78.     vector<int> v2 = {6, 1, 2, 4, -2, 2, 6, 7, 10};
  79.     int sum2 = 6;
  80.    
  81.     print_vector(v1);
  82.     std::cout << std::endl;
  83.     std::cout << sum1 << std::endl << "Values:" << std::endl;
  84.     print_vector(find_values(v1, sum1));
  85.     std::cout << "Indexes:" << std::endl;
  86.     print_vector(find_indexes(v1, sum1));
  87.     std:cout << "---------------" << std::endl;
  88.     print_vector(v2);
  89.     std::cout << std::endl;
  90.     std::cout << sum2 << std::endl << "Values:" << std::endl;
  91.     print_vector(find_values(v2, sum2));
  92.     std::cout << "Indexes:" << std::endl;
  93.     print_vector(find_indexes(v2, sum2));
  94.  
  95.     return 0;
  96. }
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