LeetCode 2215. 找出两数组的不同

2026-07-14 HGNULB 约 12 分钟

文章信息 3 个分类 2 个标签

分类

题目描述

✅ 2215. 找出两数组的不同

题意分析

给定两个整数数组 nums1 和 nums2，返回一个长度固定为 2 的列表 answer：answer[0] 装所有出现在 nums1 但不出现在 nums2 中的整数，answer[1] 装所有出现在 nums2 但不出现在 nums1 中的整数。官方样例 nums1=[1,2,3]、nums2=[2,4,6] 的答案是 [[1,3],[4,6]]；nums1=[1,2,3,3]、nums2=[1,1,2,2] 的答案是 [[3],[]]。

第一个必须读准的信号是结果必须去重。题面对两个子列表的用词是「互不相同的整数」，所以判据只跟「一个值有没有出现过」有关，跟它出现了几次毫无关系。第二个样例里 nums1 的 3 出现了两次，答案只写一个 3 就是这个意思。这句话直接决定了承载结果的容器：如果照着原数组逐个筛选并往一个可以重复的容器里塞，[1,2,3,3] 就会吐出两个 3。更省事的做法是从一开始就用一种自带去重能力的容器来装元素，让重复在入口处就被吃掉，而不是筛完再回头做一次清理。

第二个信号是这道题问的本质是双向差集：既要「在前者里而不在后者里」，又要「在后者里而不在前者里」。这两个方向是两个独立的问题，谁也不是谁的取反——把两个数组各自去重后剩下的元素分成三类，只属于前者的、只属于后者的、两边都有的，题目要的正是第一类和第二类，而第三类两个方向都不要。所以不能只算一次再对全集取补，那会把「两边都有」的元素错当成另一个方向的答案。

剩下两点也要落实。元素可以为负，取值区间是 -1000 到 1000，这意味着不能直接把元素值当下标去开一个定长容器，负下标会当场越界，除非先把整个区间平移到非负；更稳妥的是选一种对键的取值范围不作假设的容器。另外题面明确说明返回的元素顺序不重要，两个子列表内部怎么排都算对，所以完全不必为了对齐样例的展示顺序去额外排序。约束里两个数组长度都至少为 1，不用考虑空数组；但答案里的子列表可以为空——两个数组元素集合完全相同时，返回的是两个空列表，长度仍然必须是 2。

解法：两个哈希集合互查

核心思路

把题目拆成两个前后相继的步骤，思路就完全展开了：先各自去重，再互相查询。

第一步，给两个数组各建一个集合，把各自的元素全部装进去。这一步同时解决了两件事：集合天生不收重复元素，于是「结果互不相同」这个要求在入口处就自动满足了，后面不必再做任何去重清理；同时每个集合还成了一个能被高速查询的索引。选哈希集合而不是定长数组，正是因为元素可能为负、取值也可能稀疏，而哈希集合对键的取值范围没有任何假设，负数和零都能直接放进去，不需要做下标偏移。

第二步，遍历第一个集合，逐个问「这个值在第二个集合里吗」，答否就收进第一个方向的答案；再遍历第二个集合，逐个问「这个值在第一个集合里吗」，答否就收进第二个方向的答案。关键收益就在这个「问」上：如果不建集合，判断一个值是否出现在另一个数组中就只能线性扫描那个数组一遍，单次查询是 $O(n)$，整体退化成 $O(m \times n)$ 的双重循环；集合把这次查询压到了均摊 $O(1)$，于是两个方向各自只是一趟遍历。

这两个方向是完全对称、互不干扰的：把两个集合的名字调换一下，方向一的代码就变成了方向二的代码。互不干扰这点尤其要落到实现上——两个方向都要读取两个完整的集合，所以在算方向一的时候绝不能就地修改任何一个集合。一旦把第一个集合原地删成了差集，再去算第二个方向时读到的就是被破坏过的数据。正确的做法是两个集合建好后只读，答案单独收集在另外的容器里。

正确性可以这样确认。集合去重后，一个值要么在集合里要么不在，不存在「出现几次」的中间状态，而题目的判据恰好也只看在不在，两者严丝合缝。方向一遍历的是去重后的 nums1 元素全集，逐个用「不在 nums2 的集合里」这个条件过滤，收上来的既无重复也无遗漏；方向二同理。两个方向共同排除掉的正是两边都出现的那些值，这与题意一致。

解题步骤

建一个空集合 set1，遍历 nums1 把每个元素放进去。用集合是为了让重复元素在入口处就被吃掉，同时得到一个可以常数时间查询的索引；用哈希集合而不是定长数组是为了让负数元素直接做键，不必考虑下标偏移。

同样建 set2，遍历 nums2 把每个元素放进去。两个集合必须分开建，因为后面要靠「元素属于哪个集合」来区分方向，塞进同一个容器就丢掉了来源信息。

建一个空列表 only1，遍历 set1 中的每个元素，若它不在 set2 中就收进 only1。遍历 set1 而不是原数组 nums1，是因为 set1 已经去重，逐个筛出来的结果天然互不相同。

建一个空列表 only2，遍历 set2 中的每个元素，若它不在 set1 中就收进 only2。这一步和上一步完全对称，只是两个集合的角色互换；注意上一步全程没有修改过任何集合，所以这里读到的 set1 仍然是完整的。

按顺序把 only1、only2 装进结果并返回。即使某个列表是空的也必须占位，返回值的长度恒为 2。

以 nums1=[1,2,3,3], nums2=[1,1,2,2] 走一遍：装完集合后 set1 是 {1, 2, 3}——nums1 里两个 3 被集合合并成一个；set2 是 {1, 2}——nums2 里的两个 1 和两个 2 也各自合并。方向一遍历 set1：1 在 set2 中，跳过；2 在 set2 中，跳过；3 不在 set2 中，收进 only1，于是 only1 = [3]。方向二遍历 set2：1 在 set1 中，跳过；2 在 set1 中，跳过，于是 only2 = []。最终返回 [[3], []]，与样例一致。注意 only1 里只有一个 3 而不是两个，这正是「用集合承载」在起作用。

再看一个两数组元素完全相同的用例 nums1=[1,2,3], nums2=[1,2,3]：set1 和 set2 都是 {1, 2, 3}。方向一遍历 set1，1、2、3 全都能在 set2 里查到，无一入选，only1 = []；方向二同理，only2 = []。返回 [[], []]——两个空列表，但结果的长度依然是 2，不能因为都空了就少返回一个。

代码实现

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();

        for (int num : nums1) {
            // 集合天生去重，负数也能直接当键，不需要下标偏移。
            set1.add(num);
        }

        Set<Integer> set2 = new HashSet<>();

        for (int num : nums2) {
            set2.add(num);
        }

        List<Integer> only1 = new ArrayList<>();

        for (int num : set1) {
            // 方向一：遍历已去重的 set1，查 set2 是均摊 O(1)。
            if (!set2.contains(num)) {
                only1.add(num);
            }
        }

        List<Integer> only2 = new ArrayList<>();

        for (int num : set2) {
            // 方向二与方向一完全对称；全程没有修改过集合，这里读到的 set1 是完整的。
            if (!set1.contains(num)) {
                only2.add(num);
            }
        }

        List<List<Integer>> answer = new ArrayList<>();
        // 即使某个列表为空也必须占位，返回值长度恒为 2。
        answer.add(only1);
        answer.add(only2);

        return answer;
    }
}

func findDifference(nums1 []int, nums2 []int) [][]int {
    set1 := make(map[int]struct{}, len(nums1))

    for _, num := range nums1 {
        // struct{} 不占空间，这里只用键来表示集合成员。
        set1[num] = struct{}{}
    }

    set2 := make(map[int]struct{}, len(nums2))

    for _, num := range nums2 {
        set2[num] = struct{}{}
    }

    // 初始化为空切片而非 nil，否则空结果会被序列化成 null。
    only1 := []int{}

    for num := range set1 {
        // 方向一：查 set2，双值写法可以区分「键不存在」。
        if _, ok := set2[num]; !ok {
            only1 = append(only1, num)
        }
    }

    only2 := []int{}

    for num := range set2 {
        // 方向二与方向一完全对称，只是两个集合角色互换。
        if _, ok := set1[num]; !ok {
            only2 = append(only2, num)
        }
    }

    return [][]int{only1, only2}
}

复杂度分析

时间复杂度：$O(m + n)$，$m$ 与 $n$ 分别为 nums1 与 nums2 的长度。两次建集合各遍历一个数组一次；两个方向的筛选遍历的是去重后的集合，元素个数分别不超过 $m$ 与 $n$，每次哈希查询与插入平均为 $O(1)$。

空间复杂度：$O(m + n)$，最坏情况下两个数组内部都无重复元素，两个集合合计要存 $m + n$ 个元素；两个结果列表的总长度也不超过 $m + n$。

关键点总结

题目要求结果「互不相同」时，直接用集合去承载元素、让重复在入口处被吃掉，而不是先按原数组筛选再回头做一次去重清理——后者多一趟遍历，还容易漏掉。

双向差集必须分别做两次，不能只算一个方向再对全集取补：两边共有的元素在两个方向上都要被排除，取补会把它们错误地划给另一个方向。

需要反复回答「某个值在不在这堆数据里」时，先把那堆数据建成哈希集合，把单次查询从线性扫描的 $O(n)$ 降到均摊 $O(1)$，整体也就从 $O(m \times n)$ 降到 $O(m + n)$。

同一份数据要被多个步骤读取时，任何一步都不能就地修改它；差集的两个方向都要读完整的两个集合，想省一个容器而原地删除，第二个方向读到的就是脏数据。

键的取值范围决定容器选择：范围小且非负可以用定长数组，含负数或范围未知就用哈希集合，或者对下标做统一偏移。

返回值形状是题面的一部分：说了长度为 2 就必须两个位置都占上，子列表为空也要放一个空列表进去。

面试视角：这题写成一行 Stream 或 retainAll/removeAll 的链式调用只会让面试官怀疑你在回避手写逻辑，白板上更该给出两个集合加两趟对称循环的直白结构；同时对方一定会追问结果是否去重，主动说出「用集合承载所以天然去重」比被问出来更有分。

易错点总结

按原数组筛选并把结果塞进列表，用列表而不是集合承载：喂 nums1=[1,2,3,3], nums2=[1,1,2,2] → 输出 [[3, 3], []]，两个 3 都被收了进去，正确答案是 [[3], []]；同一份代码喂 nums1=[1,1,1,2,2], nums2=[2,2] → 输出 [[1, 1, 1], []]，正确答案是 [[1], []]。重复元素越多错得越离谱，必须遍历去重后的集合而不是原数组。

只算一个方向的差集，第二个方向用取补代替：把方向二写成「set2 减去方向一的结果」，喂 nums1=[1,2,3], nums2=[2,4,6] → 输出 [[1, 3], [2, 4, 6]]，2 是两边共有的却被划进了第二个方向，正确答案是 [[1,3],[4,6]]；喂 nums1=[1,2,3,3], nums2=[1,1,2,2] → 输出 [[3], [1, 2]]，正确答案是 [[3], []]。两个方向必须各自独立地做一次筛选。

为了省容器而就地把集合删成差集：写成先 set1.removeAll(set2) 再 set2.removeAll(set1)，喂 nums1=[1,2,3], nums2=[2,4,6] → 输出 [[1, 3], [2, 4, 6]]，第二次删除时 set1 已经变成了差集 {1,3}，删不掉共有的 2；喂 nums1=[1,2,3], nums2=[1,2,3] → 输出 [[], [1, 2, 3]]，正确答案是 [[], []]，第二个方向把整个 set2 全交了出去。

只对一个数组去重，另一个方向直接遍历原数组：喂 nums1=[1,2,3], nums2=[4,4,5] → 输出 [[1, 2, 3], [4, 4, 5]]，第二个列表里的 4 出现了两次，正确答案是 [[1,2,3],[4,5]]。两个方向的去重必须都做，漏一个方向就漏一半。

复制粘贴第二个方向时忘记把查询的集合换回来：第二个循环里仍然查 set2，喂 nums1=[1,2,3], nums2=[2,4,6] → 输出 [[1,3],[]]，正确答案是 [[1,3],[4,6]]；喂 nums1=[1,2], nums2=[3,4] → 输出 [[1,2],[]]，正确答案是 [[1,2],[3,4]]。因为遍历 set2 时每个元素当然都在 set2 里，条件恒不成立，第二个列表对任何输入都是空的。

把两个数组塞进同一个集合，丢掉来源信息：喂 nums1=[1,2,3], nums2=[2,4,6] → 输出 [[],[]]，正确答案是 [[1,3],[4,6]]；喂 nums1=[1,2,3,3], nums2=[1,1,2,2] → 同样输出 [[],[]]。合成一个集合后每个元素都「见过」，任何输入都只会返回两个空列表。

子列表为空时不往结果里占位：写成「非空才 add」，喂 nums1=[1,2,3,3], nums2=[1,1,2,2] → 输出 [[3]]，长度只有 1；喂 nums1=[1,2,3], nums2=[1,2,3] → 输出 []，一个子列表都没有。正确答案的长度恒为 2，空列表也必须放进去。

Java 里用 == 比较两个装箱的 Integer：喂 nums1=[1000,200,3], nums2=[200,999] → 输出 [[3, 200, 1000], [200, 999]]，200 明明两边都有却在两个方向上都被收了进去，正确答案是 [[3,1000],[999]]；而喂 nums1=[1,2,3], nums2=[2,4,6] 却能得到正确的 [[1,3],[4,6]]——因为小整数落在 Integer 缓存范围内，== 侥幸成立。本题取值上界是 1000，超出缓存的元素随时触发，属于随数据时对时错的隐蔽错误。比较装箱整数要用 equals，或者干脆用 Set 的 contains 让它自己去比。

Go 里用 var only1 []int 声明结果切片：喂 nums1=[1,2,3,3], nums2=[1,1,2,2] → 序列化结果是 [[3],null]，空的那个方向变成了 null 而不是 []；喂 nums1=[1,2,3], nums2=[1,2,3] → 序列化结果是 [null,null]，正确答案是 [[],[]]。判题机对 null 和 [] 的判定不同，两个结果切片都要用 []int{} 初始化。

相似题目

题目	难度	考察点
349. 两个数组的交集	简单	同样是两个集合互查并要求结果去重，但只取两边共有的那一类元素，是本题被两个方向共同排除的部分
350. 两个数组的交集 II	简单	结果反而不许去重、要按较小的出现次数保留重复，集合不够用，必须换成计数表
217. 存在重复元素	简单	只在单个数组内部问有没有重复，用到集合去重的同一个性质，但不涉及两个数组之间的比对
242. 有效的字母异位词	简单	也是两个序列对比，但要求两边逐个字符的频次完全相等，关心次数而不只是在不在
1657. 确定两个字符串是否接近	中等	先判断两边出现过的字符集合是否相同（本题的双向差集为空），再比较频次的多重集合，是本题的进阶