查找数组重复元素的Java代码超时问题求助

安全阿岳

2026-8-20

问题分析与修复方案

超时核心原因

你的代码超时主要是因为**arrList.contains(arr[i])的高时间开销**：ArrayList的contains方法是线性遍历查找，时间复杂度为O(k)（k为当前列表长度）。当数组规模较大时，循环中频繁调用这个方法会让整体时间复杂度从排序的O(n log n)恶化到O(n²)，触发超时。

另外代码还有两个隐藏问题：

数组越界：循环条件i < n会导致当i = n-1时，arr[i+1]访问超出数组范围，抛出ArrayIndexOutOfBoundsException
拼写错误：Arraylist应该是ArrayList（Java类名大小写敏感）

修复后的代码

利用数组排序后重复元素连续的特性，直接判断当前元素是否和下一个元素重复，且仅在第一次遇到该重复元素时添加，完全避免contains调用：

import java.util.ArrayList;
import java.util.Arrays;

public static ArrayList<Integer> duplicates(int arr[], int n) {
    ArrayList<Integer> arrList = new ArrayList<>();
    Arrays.sort(arr);
          
    for(int i = 0; i < n - 1; i++) {
        // 仅当当前元素等于下一个，且要么是第一个元素，要么和前一个元素不同时添加
        if(arr[i] == arr[i+1]) {
            if(i == 0 || arr[i] != arr[i-1]) {
                arrList.add(arr[i]);
            }
        }
    }
    
    if(arrList.isEmpty()) {
        arrList.add(-1);
    }
    
    return arrList;
}