在HackerRank运行Java代码遇'Terminated due to timeout'问题求优化

原代码的核心问题 #

1. 时间效率低下：ArrayDeque.contains()是线性遍历操作，时间复杂度为O(m)。当n和m的规模较大（比如HackerRank的测试用例达到10^5级别），整体时间复杂度会变成O(n*m)，直接导致超时。
2. 逻辑错误：滑动窗口移除元素时，如果被移除的元素是窗口内唯一的实例，maxUnique没有做递减处理，会导致最终结果不准确。
3. 原始类型使用：Deque未指定泛型，属于不规范的写法，可能引发类型安全问题。

优化后的代码 #

import java.util.*;

public class test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Integer> deque = new ArrayDeque<>();
        Map<Integer, Integer> countMap = new HashMap<>();
        int n = in.nextInt();
        int m = in.nextInt();
        int currentUnique = 0;
        int maxUnique = 0;

        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            // 加入当前元素到窗口
            deque.addLast(num);
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            // 如果是第一次加入该元素，唯一数+1
            if (countMap.get(num) == 1) {
                currentUnique++;
            }

            // 窗口超过大小m时，移除队首元素
            if (deque.size() > m) {
                int removedNum = deque.removeFirst();
                countMap.put(removedNum, countMap.get(removedNum) - 1);
                // 如果移除后该元素计数为0，唯一数-1
                if (countMap.get(removedNum) == 0) {
                    currentUnique--;
                }
            }

            // 更新最大唯一数，只有当窗口大小达到m时才统计
            if (deque.size() == m) {
                if (currentUnique > maxUnique) {
                    maxUnique = currentUnique;
                }
            }
        }
        System.out.println(maxUnique);
    }
}

优化说明 #

• 时间复杂度优化：使用HashMap记录元素出现次数，所有增删查操作都是O(1)，整体时间复杂度降至O(n)，完全适配大数据量测试用例。
• 修复逻辑错误：移除窗口元素时，同步更新计数，当元素计数归0时减少当前唯一数，保证统计准确。
• 规范泛型使用：给Deque指定Integer泛型，避免类型安全警告。
• 滑动窗口逻辑简化：统一处理每个元素的加入，不再分i=0的特殊情况，代码更简洁。

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