找到两个数组中的公共元素

难度: Easy

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们分别含有 n 和 m 个元素。

请你计算以下两个数值：

统计 0 <= i < n 中的下标 i ，满足 nums1[i] 在 nums2 中至少出现了一次。
统计 0 <= i < m 中的下标 i ，满足 nums2[i] 在 nums1 中至少出现了一次。

请你返回一个长度为 2 的整数数组 answer ，按顺序 分别为以上两个数值。

示例 1：

输入：nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
输出：[3,4]
解释：分别计算两个数值：
- nums1 中下标为 1 ，2 和 3 的元素在 nums2 中至少出现了一次，所以第一个值为 3 。
- nums2 中下标为 0 ，1 ，3 和 4 的元素在 nums1 中至少出现了一次，所以第二个值为 4 。

示例 2：

输入：nums1 = [3,4,2,3], nums2 = [1,5]
输出：[0,0]
解释：两个数组中没有公共元素，所以两个值都为 0 。

提示：

n == nums1.length
m == nums2.length
1 <= n, m <= 100
1 <= nums1[i], nums2[i] <= 100

Submission

运行时间: 32 ms

内存: 16.6 MB

class Solution:
    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        return [
            sum(1 for num in nums1 if num in set2),
            sum(1 for num in nums2 if num in set1)
        ]

Explain

此题解使用了集合来找出两个数组中的公共元素。首先，将nums1和nums2转换为集合set1和set2，这样可以去除重复元素，并且利用集合的高效查找特性。然后，分别计算nums1中有多少个元素存在于set2中，以及nums2中有多少个元素存在于set1中。这两个计数结果构成了最终的返回值。

时间复杂度: O(n + m)

空间复杂度: O(n + m)

# 添加了注释的题解代码

class Solution:
    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)  # 将nums1转换为集合，去除重复元素并提供快速查找
        set2 = set(nums2)  # 将nums2转换为集合，同上
        # 计算nums1中有多少元素在nums2的集合中出现
        count1 = sum(1 for num in nums1 if num in set2)
        # 计算nums2中有多少元素在nums1的集合中出现
        count2 = sum(1 for num in nums2 if num in set1)
        return [count1, count2]  # 返回结果数组

Explore

集合（Set）在Python中是基于哈希表实现的，这使得其查找操作的时间复杂度平均为O(1)，远比列表的O(n)要高效。使用集合可以快速地检查一个元素是否存在于集合中，这对于本题中需要频繁进行元素查找的操作非常有利。此外，集合自动去除重复元素，这也简化了处理过程。

使用生成器表达式而非列表推导的主要优点是内存效率。生成器表达式会产生一个生成器对象，它是一个迭代器，按需计算每个元素，而不是一次性地将所有元素计算出来并存储在内存中。这意味着对于大数据集处理时，可以减少程序的内存使用，提高效率。

一个更直观的实现方式是使用集合的交集操作，例如 `len(set1 & set2)` 来直接计算两个集合中共同元素的数量。这不仅代码更简洁，而且利用了集合操作的内部优化，可能在某些情况下比手动迭代检查每个元素更高效。

在这个题解中，使用的集合并不考虑元素的顺序，只关注元素是否存在。因此，无论数组中元素的顺序如何变化，只要元素的内容不变，最终的输出结果（即两个数组中公共元素的数量）是不会受到影响的。这是因为集合是一种无序的数据结构，只关心元素的存在与否。