fueanta

*Index pair of which the the sum of their value is given.

May 30th, 2017
128
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. class Solution {
  8. public:
  9.     vector<int> twoSum(vector<int>& nums, int target) {
  10.         unordered_map<int, int> seenValueIndex; // whenever we observe a value, we'll keep its
  11.         // value as key and index as value
  12.  
  13.         vector<int> pair; // resulted indexes
  14.        
  15.         for (int i = 0; i < nums.size(); i++)
  16.         {
  17.             int compliment = target - nums[i]; // sum - value at index
  18.             if (seenValueIndex.find(compliment) != seenValueIndex.end())
  19.             { // if found
  20.                 pair.push_back(seenValueIndex[compliment]);
  21.                 pair.push_back(i);
  22.                 break;
  23.             }
  24.             seenValueIndex[nums[i]] = i; // key = value, value = index
  25.         }
  26.         return pair;
  27.     }
  28. };
  29.  
  30. int main(void)
  31. {
  32.     cout << "How many elements? : ";
  33.     int size; cin >> size;
  34.  
  35.     vector<int> list;
  36.     for (int i = 0; i < size; i++)
  37.     {
  38.         cout << "\nElement NO. " << (i + 1) << " : ";
  39.         int element;
  40.         cin >> element;
  41.         list.push_back(element);
  42.     }
  43.  
  44.     cout << "\nTarget sum : ";
  45.     int target;
  46.     cin >> target;
  47.  
  48.     Solution s;
  49.     vector<int> result = s.twoSum(list, target);
  50.  
  51.     cout << endl << "Resultant pair (if exists): [";
  52.  
  53.     int count = 0;
  54.     for (int i : result)
  55.     {
  56.         ++count;
  57.         if (count % 2 != 0)
  58.         {
  59.             cout << i + 1 << ", ";
  60.         }
  61.         else
  62.         {
  63.             cout << i + 1;
  64.         }
  65.     }
  66.  
  67.     if (count == 0)
  68.         cout << "-";
  69.  
  70.     cout << "]\n\n";
  71.     return 0;
  72. }
RAW Paste Data