349. 两个数组的交集

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

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

示例 2:

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

说明:

• 输出结果中的每个元素一定是唯一的。
• 我们可以不考虑输出结果的顺序。

解题思路

使用哈希表统计一个数组中每个元素的出现次数，然后遍历另一个数组，找到与哈希表中相同元素，将其添加到结果集中。

C#代码实现

public int[] Intersection(int[] nums1, int[] nums2) {
    // 创建一个HashSet，用于存储nums1中的元素
    HashSet<int> set1 = new HashSet<int>(nums1);
    // 创建一个HashSet，用于存储nums2中的元素
    HashSet<int> set2 = new HashSet<int>();

    // 遍历nums2，如果nums1中包含nums2中的元素，则将其添加到set2中
    foreach (int num in nums2) {
        if (set1.Contains(num)) {
            set2.Add(num);
        }
    }

    // 返回set2中的元素
    return set2.ToArray();
}

C代码实现

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int* result = (int*)malloc(sizeof(int) * (nums1Size > nums2Size ? nums2Size : nums1Size));
    int resultSize = 0;
    
    int* set1 = (int*)malloc(sizeof(int) * nums1Size);
    int* set2 = (int*)malloc(sizeof(int) * nums2Size);
    int set1Size = 0;
    int set2Size = 0;

    // 构建哈希表 set1
    for (int i = 0; i < nums1Size; i++) {
        if (!contains(set1, set1Size, nums1[i])) {
            set1[set1Size++] = nums1[i];
        }
    }

    // 遍历数组 nums2，找到与 set1 中相同的元素，将其添加到 set2
    for (int i = 0; i < nums2Size; i++) {
        if (contains(set1, set1Size, nums2[i]) && !contains(set2, set2Size, nums2[i])) {
            set2[set2Size++] = nums2[i];
        }
    }

    // 将 set2 转为数组 result
    for (int i = 0; i < set2Size; i++) {
        result[resultSize++] = set2[i];
    }

    *returnSize = resultSize;
    return result;
}

// 判断数组中是否包含某个元素
bool contains(int* arr, int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return true;
        }
    }
    return false;
}

时间复杂度和空间复杂度

• 时间复杂度：O(m + n)，其中 m 和 n 分别是数组 nums1 和 nums2 的长度。分别遍历两个数组一次。
• 空间复杂度：O(m + n)，其中 m 和 n 分别是数组 nums1 和 nums2 的长度。使用了两个哈希表。