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

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

题目：

代码：

class Solution {
public:
    // 函数功能：求两个数组的交集
    // 参数：两个整型vector数组的引用
    // 返回值：包含交集元素的vector
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 构造两个set，利用set自动去重和排序的特性
        // 用nums1和nums2的迭代器区间初始化set
        set<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的特性自动去重和排序
   • 双指针遍历的方式效率高
   • 代码简洁易懂