LeetCode 349. 兩個數組的交集：Java 多種解法與性能分析

LeetCode 349. 兩個數組的交集：Java 多種解法與性能分析

題目描述

給定兩個數組，編寫函數計算它們的交集。

示例：nums1 = [1,2,2,1], nums2 = [2,2] → 返回 [2]

要求：結果元素唯一，順序不限。

解法演進：從暴力到最優

解法一：雙重循環 + ArrayList 去重 (原始代碼)

public int[] intersection(int[] nums1, int[] nums2) {
    ArrayList list = new ArrayList<>();
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            if (nums1[i] == nums2[j] && !list.contains(nums1[i])) {
                list.add(nums1[i]);
            }
        }
    }
    int[] result = new int[list.size()];
    for (int i = 0; i < list.size(); i++) result[i] = list.get(i);
    return result;
}

複雜度：時間 O(m×n)，空間 O(min(m,n))。缺點：list.contains 為 O(k)，總體接近 O(m×n×k)，大數據極慢。

解法二：HashSet 去重 + 遍歷查找 (推薦通用解)

public int[] intersection(int[] nums1, int[] nums2) {
    Set set1 = new HashSet<>();
    for (int n : nums1) set1.add(n);
    
    Set resultSet = new HashSet<>();
    for (int n : nums2) {
        if (set1.contains(n)) resultSet.add(n);
    }
    
    int[] result = new int[resultSet.size()];
    int i = 0;
    for (int n : resultSet) result[i++] = n;
    return result;
}

複雜度：時間 O(m+n)，空間 O(m+n)。優勢：HashSet 查找/插入 O(1)，自動去重，代碼簡潔。

解法三：Java 8 Stream 一行流 (面試加分項)

public int[] intersection(int[] nums1, int[] nums2) {
    Set set1 = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
    return Arrays.stream(nums2)
                 .filter(set1::contains)
                 .distinct()
                 .mapToInt(Integer::intValue)
                 .toArray();
}

特點：函數式風格，可讀性強，性能與解法二相當 (常數因子稍大)。

解法四：排序雙指針 (無額外空間/數據已排序)

public int[] intersection(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    
    List list = new ArrayList<>();
    int i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) i++;
        else if (nums1[i] > nums2[j]) j++;
        else {
            if (list.isEmpty() || list.get(list.size()-1) != nums1[i]) {
                list.add(nums1[i]);
            }
            i++; j++;
        }
    }
    return list.stream().mapToInt(Integer::intValue).toArray();
}

複雜度：時間 O(m log m + n log n)，空間 O(1) (不計結果)。適用：內存受限、數據已排序、或需輸出有序交集。

解法五：位圖/數組標記 (數值範圍小且非負)

public int[] intersection(int[] nums1, int[] nums2) {
    // 假設數值範圍 0-1000
    boolean[] seen = new boolean[1001];
    for (int n : nums1) seen[n] = true;
    
    List list = new ArrayList<>();
    for (int n : nums2) {
        if (seen[n]) {
            list.add(n);
            seen[n] = false; // 防止重複添加
        }
    }
    return list.stream().mapToInt(Integer::intValue).toArray();
}

複雜度：時間 O(m+n)，空間 O(Range)。極快但受數值範圍限制。

性能對比總結

核心考點總結

• 去重策略：HashSet 自動去重 vs 手動檢查
• 查找優化：O(1) HashSet vs O(n) 列表遍歷
• 空間換時間：額外 Set/數組換取線性時間
• 邊界處理：空數組、全重複、無交集、大數據量
• 擴展思考：若要求輸出有序？若數組極大無法全載入內存 (外部排序/分治)？若為流式數據？

面試加分回答模板

「首先用 HashSet 存儲較小數組元素實現 O(1) 查找與去重，遍歷另一數組檢查交集收集到結果 Set，最後轉數組返回。時間 O(m+n)，空間 O(m+n)。若內存極受限可排序雙指針 O(1) 空間；若數值範圍小用位圖極快。Java 8 Stream 可一行實現展示函數式思維。」