Find the Difference of Two Arrays

題目描述

給定兩個整數陣列 nums1 和 nums2，回傳一個長度 2 的列表：

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],[]]

解題思路

建 Set

將兩個陣列分別轉成 HashSet，自動去除重複元素。例如 [1,2,3] → Set{1,2,3}

差集 1

遍歷 set1 的每個元素，若不在 set2 中則加入結果。例如 1 不在 set2 → 收集

差集 2

遍歷 set2 的每個元素，若不在 set1 中則加入結果。例如 4 不在 set1 → 收集

回傳

將兩個差集結果組成二維列表回傳

程式碼

C#

csharp

public class Solution {
    public IList<IList<int>> FindDifference(int[] nums1, int[] nums2) {
        var set1 = new HashSet<int>(nums1);
        var set2 = new HashSet<int>(nums2);
        return new List<IList<int>> {
            set1.Where(x => !set2.Contains(x)).ToList(),
            set2.Where(x => !set1.Contains(x)).ToList()
        };
    }
}

TypeScript

typescript

function findDifference(nums1: number[], nums2: number[]): number[][] {
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);
    return [
        [...set1].filter(x => !set2.has(x)),
        [...set2].filter(x => !set1.has(x))
    ];
}

Python

python

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

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n + m) | O(n + m) |

建 Set 分別遍歷兩個陣列 O(n) 和 O(m)，差集遍歷 Set 各 O(n) 和 O(m)，每次查找 O(1)，因此總時間 O(n+m)。空間上兩個 Set 各存不重複元素，最壞 O(n+m)。

邊界情況

兩個陣列完全相同：例如 nums1 = nums2 = [1,2,3]，差集都是空集，回傳 [[], []]
兩個陣列完全不重疊：例如 nums1 = [1,2], nums2 = [3,4]，回傳 [[1,2], [3,4]]
陣列有大量重複：例如 nums1 = [1,1,1], nums2 = [1,1,1]，Set 去重後都是 {1}，差集為空

圖解

nums1: {1,2,3}

不在 set2 的→

nums2: {2,4,6}

不在 set1 的→

set1 - set2 = {1,3}

→

set2 - set1 = {4,6}

→

[[1,3],[4,6]]

圖表展示差集運算：set1 和 set2 的交集是 {2}，set1 去掉交集剩 {1,3}，set2 去掉交集剩 {4,6}。兩個差集分別成為答案的兩個子列表。

進階觀點

💡面試追問

Q: 為什麼用 Set 而不是排序？ A: Set 的 contains 查找是 O(1)，差集遍歷一次即可，總時間 O(n+m)。排序法需要 O(n log n + m log m) 排序後再用雙指針合併，時間和程式碼複雜度都更高。
Q: Python 的 set 差集運算子 - 做了什麼？ A: set1 - set2 等同於 set1.difference(set2)，回傳一個新 Set，包含在 set1 中但不在 set2 中的所有元素。內部實作是遍歷 set1，逐一檢查是否在 set2 中。
Q: 如果要保留重複元素（不去重）怎麼辦？ A: 不能用 Set 做差集。改用 Counter（多重集合）：統計每個元素的出現次數，然後用 Counter 的減法運算。例如 Python 的 Counter(nums1) - Counter(nums2) 會保留差異次數。

理解測驗

🤔 為什麼要先轉 Set 再做差集？

🤔 nums1 = [1,1,1], nums2 = [1,1,1] 的結果是什麼？