陣列差集計算：從 O(N²) 雙層循環到 O(N) HashSet 實戰優化

問題場景

給定兩個字串陣列 str1、str2，需分別輸出：

• 在 str1 中但不在 str2 中的元素
• 在 str2 中但不在 str1 中的元素

即計算**對稱差集**（Symmetric Difference）。

反面教材：雙層循環暴力法（O(N×M)）

// 代碼 1：str1 - str2
for (int i = 0; i < str1.length; i++) {
    boolean has = false;
    for (int j = 0; j < str2.length; j++) {
        if (str1[i].equals(str2[j])) { has = true; break; }
    }
    if (!has) println(str1[i] + " 在 str1 中，不在 str2 中");
}
// 代碼 2：str2 - str1（結構完全重複）...

缺陷：

• 時間複雜度 O(N × M)，資料量達萬級即明顯卡頓。
• 邏輯重複，維護成本高。
• 嵌套循環破壞緩存局部性，CPU 流水線利用率低。

正解：HashSet 集合運算（O(N + M)）

Set<String> set1 = new HashSet<>(Arrays.asList(str1));
Set<String> set2 = new HashSet<>(Arrays.asList(str2));

// set1 - set2
Iterator<String> it = set1.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (set2.contains(s)) {
        set2.remove(s); // 從 set2 移除共同元素
    } else {
        println(s + " 在 str1 中，不在 str2 中");
    }
}
// 剩餘 set2 即為 str2 獨有
for (String s : set2) {
    println(s + " 在 str2 中，不在 str1 中");
}

核心優勢解析

進階：Java 8+ Stream 風格（更簡潔）

List<String> onlyIn1 = Arrays.stream(str1)
    .filter(s -> !set2.contains(s))
    .distinct()
    .collect(Collectors.toList());

List<String> onlyIn2 = Arrays.stream(str2)
    .filter(s -> !set1.contains(s))
    .distinct()
    .collect(Collectors.toList());

移動端/嵌入式特別提示

• Android 早期 Dalvik/ART 對 HashSet 有額外開銷，但仍遠優於雙層循環。
• 極度受限環境（如 < 64KB RAM）可考慮**位圖**（元素範圍小）、**排序後雙指針**（O(N log N) 但無額外空間）、**布隆過濾器**（允許誤判）。

泛化：任意類型的差集計算

只要實現 equals() / hashCode() 契約，同樣適用於自定義對象：

class User { Long id; String name; /* 正確重寫 equals/hashCode */ }
Set<User> set1 = new HashSet<>(list1);
Set<User> set2 = new HashSet<>(list2);
// 後續邏輯不變

總結

「用空間換時間」是經典權衡。HashSet 基於雜湊表，將查找從 O(N) 降為 O(1)，將雙層循環的 O(N²) 降為 O(N)。這不是「技巧」，而是**正確選擇資料結構**的基本功。遇到「判斷元素是否存在於集合」、「去重」、「求交/並/差集」等場景，**第一反應應是 Set/Map**，而非循環。