查找两个有序数组的公共部分

#include <iostream>
 #include <vector>
 #include <unordered_set>
 
 using std::cout;
 using std::endl;
 using std::cin;
 using std::vector;
 using std::unordered_set;
 
 //查找两个有序数组的公共部分
 //不去重版本
 vector<int> getIntersection(const vector<int>& nums1, const vector<int>& nums2) {
     vector<int> result;
 
     int p1 = 0;
     int p2 = 0;
     while(p1 < nums1.size() || p2 < nums2.size()) {
         if(nums1[p1] == nums2[p2]) {
             result.push_back(nums1[p1]);
             ++p1;
             ++p2;
         }   
         else if(nums1[p1] > nums2[p2]) {
             ++p2;
         }   
         else {
             ++p1;
         }   
     }   
     return result;
 }

 void print(const vector<int>& vec) {
     for(int i : vec) {
         cout << i << ' ';
     }
     cout << endl;
 }
 
 int main() {
     vector<int> v1 = { 1,2,2,3,4,5,5,5,8,9,11,13 };
     vector<int> v2 = { 2,2,2,3,5,6,7,7,8,9,10,12,12,13,13,14 };
     print(v1);
     print(v2);
 
     vector<int> ret = getIntersection(v1, v2);
     print(ret);
     vector<int> ret2 = getIntersection2(v1, v2);
     print(ret2);
     vector<int> ret3 = getIntersection3(v1, v2);
     print(ret3);
 }   

[leetcode 349. 两个数组的交集（有相同的数字） | 张威的编程学习笔记 (gitee.io)](https://iszhwei.gitee.io/algo/03 哈希算法/349.两个数组的交集.html)

 //去重版
 vector<int> getIntersection2(const vector<int>& nums1, const vector<int>& nums2) {
     unordered_set<int> result_set;
     unordered_set<int> nums_set(nums1.begin(), nums1.end());
 
     for(int num : nums2) {
         if(nums_set.find(num) != nums_set.end()) {
             result_set.insert(num);
         }
     }
 
     return vector<int>(result_set.begin(), result_set.end());
 }

 //因为set比数组占用的空间大，并且set把数值映射到key都要做hash计算，速度也比数组慢
 //如果数组数值范围可控可以使用数组做hash
 const int M = 20;   //数值的范围
 vector<int> getIntersection3(const vector<int>& nums1, const vector<int>& nums2) {
     unordered_set<int> result_set;  //给结果去重
     int hashTable[M] = {0};
     for(int num : nums1) {
         hashTable[num] = 1;
     }
 
     for(int num : nums2) {
         if(hashTable[num] == 1) {
             result_set.insert(num);
         }
     }
     return vector(result_set.begin(), result_set.end());
 }