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

这条线的点是什么？

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

我在你的代码中看不到任何慢的东西。我只是想知道如何使用集合来跟踪唯一的数字，因为集合只告诉你是否有这样的数字(但不知道同一个数字出现了多少次(。你不想一直扫描deque，看看被删除的数字是否是最后一个。

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

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);
}
}

我只是想分享一下我是如何解决的，以防有帮助。

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque deque = new ArrayDeque();
Set<Integer> integers = new HashSet<>();
int n = in.nextInt();
int m = in.nextInt();
long result = 0;
for (int i = 0; i < n; i++) {
int num = in.nextInt();
deque.add(num);
integers.add(num);
if (deque.size() == m) {
long currentSize = integers.size();
if (currentSize > result) {
result = currentSize;
}
Integer removed = (Integer) deque.pollFirst();
if (!deque.contains(removed)) {
integers.remove(removed);
}
}
}
System.out.println(result);
}

我们可以通过一起避免哈希图来稍微优化空间，但Hackerrank似乎并不关心这一点。任何我如何将我的解决方案放在这里，它可以通过使用地图来解决这个问题。

private int countUniqueNumsInSubarrays(int[] nums, int m) {
Deque<Integer> deque = new LinkedList<>();
int maxUniqueCount = 0;
for (int i = 0; i < nums.length; i++) {
// if deque's left entry is outside the window then pop it out
while (!deque.isEmpty() && i - deque.peekFirst() >= m) {
deque.removeFirst();
}
// this will make sure that the deque only contains unique numbers,
// this is essentially helps us avoid that extra hash map  
while (!deque.isEmpty() && nums[deque.peekLast()] == nums[i]) {
deque.removeLast();
}
deque.addLast(i);
if (i >= m - 1) {
maxUniqueCount = Math.max(maxUniqueCount, deque.size());
}
}
return maxUniqueCount;
}

import java.util.*;
public class test {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque<Integer> deque = new ArrayDeque<>();
int n = in.nextInt();
int m = in.nextInt();
int maxUnique = 0;
Map<Integer, Boolean> uniqSet = new HashMap<>();
for (int i = 0; i < n; i++) {
int num = in.nextInt();
deque.addLast(num);
uniqSet.put(num, true);
if(deque.size() == m){
//  int uniqueSize = new HashSet<>(deque).size();
int uniqueSize = uniqSet.size();
maxUnique = Math.max(maxUnique, uniqueSize);

int x = deque.removeFirst();
if(!deque.contains(x)){
uniqSet.remove(x);
}
}
}
in.close();
System.out.println(maxUnique);
}
}

我们没有试图从hashSet中删除元素，而是只从deque中删除不再在窗口中的元素。如果元素不在deque中，则意味着它不再在窗口中，因此我们将其从hashSet中删除。

我们检查hashSet.size((是否大于max以更新唯一元素的最大计数。

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