【C++习题】20. 两个数组的交集

题目：349. 两个数组的交集 - 力扣（LeetCode）

链接🔗：349. 两个数组的交集 - 力扣（LeetCode）

题目：

---

代码：

class Solution {
public:// 函数功能：求两个数组的交集// 参数：两个整型vector数组的引用// 返回值：包含交集元素的vectorvector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 构造两个set，利用set自动去重和排序的特性// 用nums1和nums2的迭代器区间初始化setset<int> s1(nums1.begin(), nums1.end());  // nums1中的不重复元素set<int> s2(nums2.begin(), nums2.end());  // nums2中的不重复元素// 创建结果数组，用于存储交集元素vector<int> ret;// 获取两个set的起始迭代器auto it1 = s1.begin();auto it2 = s2.begin();// 同时遍历两个set，直到其中一个遍历完while(it1 != s1.end() && it2 != s2.end()){if(*it1 < *it2)  {// 如果s1当前元素小，移动s1的迭代器it1++;}else if(*it1 > *it2){// 如果s2当前元素小，移动s2的迭代器it2++;}else  // *it1 == *it2{// 相等说明是交集元素ret.push_back(*it1);  // 将交集元素加入结果数组// 两个迭代器都要往后移动it1++;it2++;}}return ret;  // 返回结果数组}
};

算法思路解析：

1. 预处理：
   • 将两个数组转换为set，实现去重和排序
   • 时间复杂度：O(NlogN)，空间复杂度：O(N)
2. 求交集：
   • 利用set有序的特性，用双指针（迭代器）同时遍历两个set
   • 类似归并排序的思路，比较两个当前元素：
     • 如果s1当前元素小，移动s1迭代器
     • 如果s2当前元素小，移动s2迭代器
     • 如果相等，就是交集元素，加入结果数组，两个迭代器都移动
   • 时间复杂度：O(min(N,M))，N和M是两个set的大小
3. 优势：
   • 利用set的特性自动去重和排序
   • 双指针遍历的方式效率高
   • 代码简洁易懂