Java Deque(从子数组中查找唯一整数的最大数量。)

Question

我试图解决 Java Deque 上的 HackerRank 问题。除了具有 100,000 个输入的案例之外，我的代码通过了所有案例。

问题:在这个问题中，给你 N 个整数。您需要在大小为 M 的所有可能的连续子数组中找到唯一整数的最大数目。 --->所以我们得到了 N 个整数，并且需要在每个传染性子数组(大小为 M)中找到“唯一整数”的数量。然后打印那些“唯一整数”的最大数量。

link: https://www.hackerrank.com/challenges/java-dequeue/problem

我的代码:

public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            Deque deque = new ArrayDeque<>();
            HashSet<Integer> set = new HashSet<>();
            int n = in.nextInt();
            int m = in.nextInt();
            int max=0;
            for (int i = 0; i < n; i++) {
                int num = in.nextInt();
                deque.add(num);
                set.add(num);
                if(i>=m-1){
                    if(set.size()>max)max=set.size();
                    Integer removed=(Integer)deque.removeFirst();
                    set.remove(removed);
                   set.add((Integer)deque.peek());
                }
                
            }
            System.out.println(max);
        }

请告诉我我的代码哪里出错了。

Answer 1

这行有什么意义？

                   set.add((Integer)deque.peek());

我在您的代码中没有看到任何缓慢的地方。我只是想知道如何使用集合来跟踪唯一数字，因为集合只告诉您是否有这样的数字(但不会告诉您同一数字出现了多少次)。而且您不想继续扫描双端队列以查看被删除的数字是否是最后一个。

我不认为这是很棒/快速的代码，但它似乎通过了测试用例。我通过使用 map (并使用您的一些代码)来计算窗口中每个整数的数量。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Integer> deque = new ArrayDeque<>();
        HashMap<Integer, Integer> counts = new HashMap<>();
        int n = in.nextInt();
        int m = in.nextInt();
        int max = 0;
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            deque.add(num);
            int count = counts.getOrDefault(num, 0);
            counts.put(num, ++count);
            if (i >= m - 1) {
                if (counts.size() > max) max = counts.size();
                Integer removed = deque.removeFirst();
                int removing = counts.get(removed);
                removing--;
                if (removing == 0) {
                    counts.remove(removed);
                } else {
                    counts.put(removed, removing);
                }
            }
        }
        System.out.println(max);
    }

}