统计数组重复元素的代码提交时出现TLE错误，求问题分析

你的代码超时是因为采用了双重循环遍历数组，时间复杂度为O(g²)，当数组长度g较大时，这种方法的效率会急剧下降，直接导致超出时间限制。

优化思路 #

改用哈希表统计每个元素的出现频率，再通过组合数公式计算重复对数：

• 对于一个出现了k次的元素，它能形成的重复对数量是 k*(k-1)/2（从k个元素中选2个的组合数）
• 这种方法的时间复杂度为O(g)，能高效处理大规模数组

优化后的代码 #

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int g = Integer.parseInt(br.readLine());
            String[] parts = br.readLine().split(" ");
            Map<Integer, Integer> freqMap = new HashMap<>();
            for (String part : parts) {
                int num = Integer.parseInt(part);
                freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
            }
            long count = 0;
            for (int freq : freqMap.values()) {
                count += (long) freq * (freq - 1) / 2;
            }
            System.out.println(count);
        }
    }
}

额外优化点 #

• 用BufferedReader替代Scanner，前者的读取速度更快，处理大量输入时能进一步减少时间消耗
• 如果题目明确给出元素的取值范围（比如元素都是0到1e5之间的整数），可以用数组代替HashMap，效率会更高，示例如下：

// 假设元素范围是0到100000
int[] freqArr = new int[100001];
for (String part : parts) {
    int num = Integer.parseInt(part);
    freqArr[num]++;
}
long count = 0;
for (int freq : freqArr) {
    count += (long) freq * (freq - 1) / 2;
}

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