c++中如何求两个数组的交集_c++数组交集实现方法

答案：C++中求两数组交集常用三种方法：①排序+双指针，时间复杂度O(m log m + n log n)，适合可排序数组；②哈希表法，时间复杂度O(m + n)，无需排序且自动去重；③STL的set_intersection，仅适用于有序数组，代码简洁但可能含重复元素。

在C++中求两个数组的交集，常见做法是利用排序和双指针，或使用哈希表来提高查找效率。以下是几种实用的实现方法，适用于不同场景。

方法一：排序 + 双指针（适合有序或可修改原数组）

如果允许对数组排序，可以先对两个数组排序，然后使用双指针遍历，找出相同的元素。

#include 
#include 
using namespace std;

vector getIntersection(vector& nums1, vector& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());

    vector result;
    int i = 0, j = 0;

    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] == nums2[j]) {
            result.push_back(nums1[i]);
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

说明：该方法时间复杂度为 O(m log m + n log n)，空间复杂度较低。若要求去重，可在插入 result 前判断是否已存在。

方法二：哈希表（适合不允许排序或需保留原始顺序）

将一个数组的元素存入 unordered_set，再遍历另一个数组检查是否存在，能快速判断交集元素。

立即学习“C++免费学习笔记（深入）”；

AVCLabs

AI移除视频背景，100%自动和免费

下载

#include 
#include 
using namespace std;

vector getIntersection(vector& nums1, vector& nums2) {
    unordered_set set1(nums1.begin(), nums1.end());
    unordered_set resultSet;

    for (int num : nums2) {
        if (set1.count(num)) {
            resultSet.insert(num); // 自动去重
        }
    }

    return vector(resultSet.begin(), resultSet.end());
}

说明：此方法时间复杂度为 O(m + n)，适合大数据量。使用 resultSet 避免重复结果。

方法三：STL 算法 set_intersection（仅适用于有序数组）

C++ 标准库提供 set_intersection 函数，可用于求两个有序序列的交集。

#include 
#include 
#include 
using namespace std;

vector getIntersection(vector& nums1, vector& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());

    vector result;
    set_intersection(nums1.begin(), nums1.end(),
                     nums2.begin(), nums2.end(),
                     back_inserter(result));
    return result;
}

说明：简洁高效，但要求输入有序，且结果可能包含重复元素（若原数组有重复），如需去重可配合 unique 使用。

基本上就这些常用方法。根据是否允许修改原数组、是否需要去重、性能要求等选择合适方案。哈希表法最通用，双指针节省内存，STL 方法代码最简洁。不复杂但容易忽略细节，比如重复元素处理。