C/C++---------------LeetCode第350. 两个数组的交集 II

题目及要求

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

双指针

思路：先排好序，定义两个指针分别指向nums1和nums2，然后哪个指针指向的值小的话就移动那个指针 ，例如排好序的数组为nums1=1,5,8 nums2=3,5,9，指针分别指向第一个元素，1和5，nums1指向的1小于nums2指向的3，移动nums1的指针到下一个，这个时候nums1指向5，nums2还是指向1，这个时候nums2比较小，这个时候移动nums2的指针，这个时候nums1和nums2都指向了5构成了交集，存入数组，当指针超出数组时退出循环返回存放交集的数组即可

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());   //排序
        sort(nums2.begin(),nums2.end());
        int len1=nums1.size(),len2=nums2.size();
        vector<int>intersection;  //存放交集
        int index1=0,index2=0;
        while(index1<len1&&index2<len2){   //超出大小的时候退出循环
            if(nums1[index1]<nums2[index2]){   //nums1小于nums2的话将指向nums1的指针右移一位
                index1++;
            }else if(nums1[index1]>nums2[index2]){
                index2++;
            }else{
                intersection.push_back(nums1[index1]);   //如果相等的话就代表是交集的数，存入intersection
                index1++;
                index2++;
            }
        }
        return intersection;
    }
};

哈希表

思路：将nums1的元素存入哈希表计数，遍历nums2检查nums2中的元素在cnts数组中的计数是否大于0，如果有出现的话就将这个元素添加到ans数组，然后cnts内的计数减去1,

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        int cnts[1001] = {};   // 根据题目提示初始化数组
        vector<int> ans;       // 存储最终结果的动态数组
        for (int &tmp: nums1) {  // 使用范围for循环遍历nums1
            cnts[tmp]++;         // 对nums1中的每个元素进行计数
        }
        for (int &tmp: nums2) {
            if (cnts[tmp] > 0) { // 首先检查nums2中的元素在cnts数组中的计数是否大于0
                ans.push_back(tmp); // 如果是，则将该元素添加到结果数组ans中
                cnts[tmp]--;       // 然后将cnts数组中对应的计数减一
            }
        }
        return ans;  // 返回结果数组
    }
};

在main内使用

nt main() {
    Solution solution; // 创建Solution对象
    vector<int> nums1 = {1, 2, 2, 1}; // 定义第一个数组
    vector<int> nums2 = {2, 2};       // 定义第二个数组
    vector<int> result = solution.intersect(nums1, nums2); // 调用intersect方法，并接收结果

    // 打印结果
    cout << "Intersection: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}