日刊競プロ ABC 210 - C - Colorful Candies-

C - Colorful Candies

問題文
N 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色 1、色 2、…、色 10**9の、10**9種類の色のうちいずれかの色をしています。i=1,2,…,N について、左から i 番目のキャンディの色は色 ci​です。高橋君は並んでいるキャンディのうち、連続して並んだ K 個のキャンディをもらうことができます。
すなわち、1≤i≤N−K+1 を満たす整数 i を選んで、 左から i 番目、i+1 番目、i+2 番目、…、i+K−1 番目のキャンディをもらうことができます。高橋君はいろいろな色のキャンディを食べたいので、 もらうキャンディに含まれる色の種類数が多いほどうれしい気持ちになります。
高橋君がもらうキャンディに含まれる色の種類数の最大値を出力してください。

制約
1≤K≤N≤3×10**5
1≤ci​≤10**9
入力はすべて整数

考えたこと

全部試すことしか思いつかずTLE。。。

以下の解説を見て再び考えた。。。

AtCoder-ABC210 C - Colorful Candies【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

まず初めに辞書を作り、１からKの範囲に含まれる数キーとして辞書を作成。

その後はi個ずつずらして考えていく。その際に0→1となったときは種類が増えたものとして種類に１を足していき、逆に1→0となったときは数の種類が減ったものとしてカウントする。

from collections import defaultdict
N,K = map(int,input().split())
clist = list(map(int,input().split()))
d =defaultdict(int)
tmp = 0
ans = 0
#0-Kの範囲で辞書を作成
for i in range(K):
 if d[clist[i]]==0:
   tmp+=1
 d[clist[i]]+=1
 
ans = tmp
for i in range(N-K):
 if d[clist[i]]==1:
   tmp-=1
 d[clist[i]]-=1
 if d[clist[i+K]]==0:
   tmp+=1
 d[clist[i+K]]+=1
 ans = max(ans,tmp)
 
print (ans)

本番で解ける気がしない。。。。