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 没有出现在 nums1 中。因此，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] = [3]。
nums2 中的每个整数都在 nums1 中出现。因此，answer[1] = []。

提示：

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

解题思路

这道题要求找出两个数组的差集，即在一个数组中存在但在另一个数组中不存在的元素。

核心思路：

  1. 使用哈希集合来存储数组中的唯一元素，可以快速判断某个元素是否存在
  2. 遍历每个数组，找出不在另一个数组中的元素
  3. 由于要求去重，可以先将数组转换为集合，再进行差集运算

解法分析：

  • 方法一（推荐）：使用集合的差集运算，直接计算两个集合的差集，代码简洁易懂
  • 方法二：手动遍历比较，使用哈希集合存储一个数组的所有元素，然后遍历另一个数组查找差异

集合差集的方法在各种语言中都有很好的支持，时间复杂度为 O(m+n)，其中 m 和 n 分别是两个数组的长度。由于需要去重，所以必须使用集合数据结构。

代码实现

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
        
        vector<int> diff1, diff2;
        
        for (int num : set1) {
            if (set2.find(num) == set2.end()) {
                diff1.push_back(num);
            }
        }
        
        for (int num : set2) {
            if (set1.find(num) == set1.end()) {
                diff2.push_back(num);
            }
        }
        
        return {diff1, diff2};
    }
};

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        set1, set2 = set(nums1), set(nums2)
        return [list(set1 - set2), list(set2 - set1)]

public class Solution {
    public IList<IList<int>> FindDifference(int[] nums1, int[] nums2) {
        var set1 = new HashSet<int>(nums1);
        var set2 = new HashSet<int>(nums2);
        
        var diff1 = new List<int>();
        var diff2 = new List<int>();
        
        foreach (int num in set1) {
            if (!set2.Contains(num)) {
                diff1.Add(num);
            }
        }
        
        foreach (int num in set2) {
            if (!set1.Contains(num)) {
                diff2.Add(num);
            }
        }
        
        return new List<IList<int>> { diff1, diff2 };
    }
}

var findDifference = function(nums1, nums2) {
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);
    
    const diff1 = [...set1].filter(x => !set2.has(x));
    const diff2 = [...set2].filter(x => !set1.has(x));
    
    return [diff1, diff2];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度值
时间复杂度O(m + n)
空间复杂度O(m + n)

其中 m 和 n 分别是 nums1 和 nums2 的长度。空间复杂度主要用于存储两个哈希集合。

相关题目