デキューのユニークな値の最大数を計算する最速の方法

Question

私は、コンソールから取った一連のn個の整数のmサイズのサブアレイの一意の値の最大数を数えます。このコードをさらに最適化する方法はありますか？ 、事前にアレックスこれはO（NM）さ

import java.util.*; 
public class test { 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     Deque deque = new ArrayDeque<>(); 
     int n = in.nextInt(); 
     int m = in.nextInt(); 
     long count = 0, c = 0; 

     for (int i = 0; i < m; i++) deque.addFirst(in.nextInt()); 
     count = deque.stream().distinct().count(); 
     for (int i = 0; i < n - m; i++) { 
      count = Math.max(count, deque.stream().distinct().count()); 

      deque.removeLast(); 
      deque.addFirst(in.nextInt()); 
     } 
     System.out.println(count); 
    } 
} 

Answer 1

（distinctを想定しているO（M）を）のをありがとうございます。 O（N）でこれを行うことは、現在ウィンドウ内にある非ゼロカウントの値の数を追跡することによって可能になります。

擬似コード：

for (int i = M; i < N; i++) { 
    counts[x[i-M]]--; 
    if (counts[x[i-M]] == 0) { 
     nonzero--; 
    } 

    if (counts[x[i]] == 0) { 
     nonzero++; 
    } 
    counts[x[i]]++; 

    maxNonzero = max(maxNonzero, nonzero); 
}