找出两数组的不同

难度: Easy

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，请你返回一个长度为 2 的列表 answer ，其中：

answer[0] 是 nums1 中所有不存在于 nums2 中的不同整数组成的列表。
answer[1] 是 nums2 中所有不存在于 nums1 中的不同整数组成的列表。

注意：列表中的整数可以按任意顺序返回。

示例 1：

输入：nums1 = [1,2,3], nums2 = [2,4,6]
输出：[[1,3],[4,6]]
解释：
对于 nums1 ，nums1[1] = 2 出现在 nums2 中下标 0 处，然而 nums1[0] = 1 和 nums1[2] = 3 没有出现在 nums2 中。因此，answer[0] = [1,3]。
对于 nums2 ，nums2[0] = 2 出现在 nums1 中下标 1 处，然而 nums2[1] = 4 和 nums2[2] = 6 没有出现在 nums2 中。因此，answer[1] = [4,6]。

示例 2：

输入：nums1 = [1,2,3,3], nums2 = [1,1,2,2]
输出：[[3],[]]
解释：
对于 nums1 ，nums1[2] 和 nums1[3] 没有出现在 nums2 中。由于 nums1[2] == nums1[3] ，二者的值只需要在 answer[0] 中出现一次，故 answer[0] = [3]。
nums2 中的每个整数都在 nums1 中出现，因此，answer[1] = [] 。

提示：

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

Submission

运行时间: 33 ms

内存: 16.3 MB

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        n1 = set(nums1)
        n2 = set(nums2)
        ans = [[],[]]
        for j in n1:
            if j not in n2:
                ans[0].append(j)
        for j in n2:
            if j not in n1:
                ans[1].append(j)
        return ans

Explain

首先，将两个数组nums1和nums2转换成集合n1和n2，以去除重复元素并利用集合的高效查找特性。接着，创建一个双元素列表ans，用于存储最终结果。遍历集合n1中的每个元素，检查它是否不在集合n2中；如果是，则将该元素添加到ans[0]中。类似地，遍历集合n2中的每个元素，检查它是否不在集合n1中；如果是，则将该元素添加到ans[1]中。最后，返回列表ans作为结果。

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

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

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        n1 = set(nums1)  # 将nums1转换为集合n1
        n2 = set(nums2)  # 将nums2转换为集合n2
        ans = [[],[]]  # 初始化答案列表
        for j in n1:  # 遍历集合n1中的每个元素
            if j not in n2:  # 如果元素不在n2中
                ans[0].append(j)  # 添加到结果的第一部分
        for j in n2:  # 遍历集合n2中的每个元素
            if j not in n1:  # 如果元素不在n1中
                ans[1].append(j)  # 添加到结果的第二部分
        return ans  # 返回结果

Explore

使用集合而不是列表的主要原因是集合提供更高效的查找、插入和删除操作，这些操作的平均时间复杂度通常为O(1)，而列表的相应操作则需要O(n)时间复杂度，特别是在查找和删除元素时。使用集合可以快速地检查一个元素是否存在于另一个集合中。虽然字典也提供相似的时间复杂度，但集合使用起来更直接且自然，因为它专为无序且唯一的元素集设计。此外，集合自动去除输入数组中的重复元素，简化了问题处理过程。

将nums1和nums2转换为集合时，自动去除数组中的重复元素，这对最终结果是必要的，因为题目要求找出两个数组独有的元素。如果不去除重复元素，那么在比较过程中可能会重复计算那些重复的元素，导致结果中同样包含重复的元素，违反了题目的要求。去重确保了每个元素只被计算一次，使得最终结果中每个数组的独有元素是唯一的。

集合内部通常实现为一个哈希表，这是一种数据结构，可以通过哈希函数将元素映射到哈希表中的一个位置（即一个桶），从而实现快速的数据访问。当我们向集合中添加一个元素或从集合中查询一个元素时，集合首先计算元素的哈希值，然后直接访问对应的桶。因为这个过程大部分时间不依赖于元素的总数，所以操作的时间复杂度平均为O(1)。然而，实际效率可能受到哈希函数质量和冲突处理策略的影响。

如果nums1和nums2中的元素数量差异很大，算法的效率可能会受到一定的影响。具体来说，如果一个集合比另一个集合大很多，那么在进行元素是否存在的检查时，较大的集合可能需要更多的时间来完成遍历，尽管每次检查的平均复杂度仍然是O(1)。此外，如果一个数组非常大，它的转换过程（数组到集合）和空间占用都会相对较高。因此，虽然理论上每个查找操作都是O(1)，实际的时间和空间效率可能会因为集合大小的极端差异而有所不同。