Java 陣列查重：雙重迴圈暴力法與效能優化思路

從 O(n²) 到 O(n) 的查重演進

判斷陣列中是否存在重複值是經典面試題。本文以 int[] 為例，先展示最直觀的雙重迴圈暴力解法，再引導至集合、排序、位圖等高效能替代方案。

暴力解法（教學用）

int[] arr = {1,10,5,8,11,100,99,10};
boolean flag = false;
for (int i = 0; i < arr.length; i++) {
    int count = 0;
    for (int j = 0; j < arr.length; j++) {
        if (arr[i] == arr[j]) count++;
    }
    if (count >= 2) { flag = true; break; } // 含自我比較故 >=2
}
System.out.println(flag ? "有重複值" : "無重複值");

缺點：時間複雜度 O(n²)，資料量大時極慢；且未標記重複值具體是哪個。

進階方案對比

最佳實踐程式碼

public static boolean hasDuplicate(int[] arr) {
    if (arr == null || arr.length <= 1) return false;
    Set<Integer> seen = new HashSet<>(arr.length * 2);
    for (int v : arr) {
        if (!seen.add(v)) return true; // add 回傳 false 表示已存在
    }
    return false;
}

// 取得所有重複值
public static Set<Integer> findDuplicates(int[] arr) {
    Set<Integer> seen = new HashSet<>(), dup = new HashSet<>();
    for (int v : arr) if (!seen.add(v)) dup.add(v);
    return dup;
}

面試加分點

• 說明為何 HashSet.add 回傳 boolean 可直接判重。
• 討論 Integer 快取範圍（-128~127）對自動裝箱效能的影響。
• 若陣列極大（億級），提及外部排序、布隆過濾器、分布式去重等方案。