方法效率疑问：检测数组重复元素的双重循环方案为何大输入超时？

让我来给你拆解这段代码的低效根源——它的核心问题在于冗余的比较逻辑和平方级的时间复杂度，这在面对大输入时会直接拖垮性能。

先看这段待分析的代码：

static boolean containsDuplicates(int[] a) { 
    boolean elementRepeat = false; 
    for (int loop1 = 0; loop1 < a.length; loop1++){ 
        for (int loop2 = 0; loop2 < a.length; loop2++){ 
            if (a[loop1] == a[loop2] && loop1!=loop2){ 
                elementRepeat = true; 
                return elementRepeat; 
            } 
        } 
    } 
    return elementRepeat; 
}

问题1：大量不必要的重复对比 #

这段代码用了两层嵌套循环，外层的每个元素都会和数组里所有元素做一次对比——包括它自己，以及已经和它比较过的元素：

• 当loop1=0时，loop2会遍历整个数组，其中loop2=0的对比完全是多余的（虽然最后用loop1!=loop2过滤掉了，但这个判断本身也是额外的开销）；
• 当loop1=1时，loop2又会从0开始遍历，这就重复比较了a[0]和a[1]两次，完全是浪费算力。

哪怕把内层循环改成从loop1+1开始，能避免部分重复，但核心的性能问题还是没解决。

问题2：O(n²)的时间复杂度是性能杀手 #

这种嵌套循环的时间复杂度是O(n²)，n是数组的长度。这意味着程序的运行时间会随着数组规模的增长呈平方级飙升：

• 如果数组有1000个元素，需要执行1000×1000=100万次比较；
• 如果数组有10000个元素，就要执行1亿次比较——这会让大数组的处理速度慢到无法接受。

更高效的替代思路 #

对比之下，有两种常见的高效方案：

• 哈希集合（HashSet）方案：遍历数组时，把每个元素加入HashSet。如果某个元素无法被加入（说明集合中已存在该元素），直接返回true。这种方法的时间复杂度是O(n)，因为哈希集合的插入和查找操作平均都是O(1)。
• 排序后遍历方案：先对数组进行排序（时间复杂度O(n log n)），然后遍历一次数组，检查相邻元素是否相等即可。这种方法不需要额外的空间（如果用原地排序的话），性能也远优于O(n²)的实现。

内容的提问来源于stack exchange，提问作者Mark F