一.題意

題意要求找到最短的包含 1 -> m 所有種類的元素的區(qū)間
對于這個區(qū)間我們可以看成一個set,
則我們需要維護的set信息有:
1: int cnt[N] :每種元素的個數(shù)
2: int now :當前種類數(shù)
3: int l,r :左右端點(不是廢話??)

二.性質&&分析

嘗試使用雙指針維護這樣一個左閉右開的區(qū)間 [l,r)
此時區(qū)間包含的元素就是 a[l]…a[r-1] , 長度為 r-l
初始情況為集合中沒有一個元素,l=r=1
我們只允許左右端點向右移動,容易發(fā)現(xiàn),左端點向右移動會使集合元素種類呈減少的趨勢,而右端點呈增加趨勢
對于每次區(qū)間移動之前,分為兩種情況:
case1: now < m :只有移動右端點,才可能找到滿足條件的集合
case2: now = m :嘗試向右移動左端點,如果now不變,說明找到了更小的區(qū)間,更新答案即可
如果now變了,進入case1

三.細節(jié)

怎么知道now有沒有變呢?
我們維護了一個cnt[N],它實時記錄了集合中各種元素的數(shù)量
當區(qū)間變化時,增加或減少元素,都需要維護cnt[N]
當元素種類數(shù)發(fā)生變化時
1:增加:只會由右端點右移引起,新添加的元素使得集合中該種元素的數(shù)量從0->1
2:減少:只會由左端點右移引起,新刪除的元素使得集合中該種元素的數(shù)量從1->0
當我們找到一個新的滿足條件的集合時,當且僅當當前區(qū)間長度小于minlen時才可以更新,這樣才能滿足題目中的相同長度區(qū)間優(yōu)先在前面 這個條件

四.code