雙指針?biāo)惴?，顧名思義，需要兩個指針，且可以做到將時間復(fù)雜度為O(n^2)的算法變?yōu)镺(n)的算法。

常見問題分類：

（1）對于一個序列，用兩個指針對一段區(qū)間進(jìn)行維護(hù)

（2）對于兩個序列，使之維護(hù)某種次序，例如歸并排序中合并兩個有序序列的操作

最長連續(xù)不重復(fù)子序列

給定一個長度為 n 的整數(shù)序列，請找出最長的不包含重復(fù)的數(shù)的連續(xù)區(qū)間，輸出它的長度。

輸入格式

第一行包含整數(shù) n。

第二行包含 n 個整數(shù)（均在 0～105 范圍內(nèi)），表示整數(shù)序列。

輸出格式

共一行，包含一個整數(shù)，表示最長的不包含重復(fù)的數(shù)的連續(xù)區(qū)間的長度。

最長連續(xù)不重復(fù)子序列思路

很明顯，這里符合“對于一個序列，用兩個指針維護(hù)一段區(qū)間”的情況，故采用雙指針?biāo)惴?strong>

1.遍歷數(shù)組a中的每個元素a[i],對于每個i，查找j，使得雙指針[j，i]保持以a[i]結(jié)尾的最長連續(xù)不重復(fù)子序列，長度為i-j+1，并將該長度和r中的較大者更新為r.

2.由于[j，i-1]是上一步得到的最優(yōu)解（正在比較中的最長連續(xù)不重復(fù)子序列），如果[j，i]中有重復(fù)元素，則一定是a[i]，所以將j向右移動，直到a[i]不重復(fù)為止。

3.用數(shù)組s記錄子序列a[j ?~ i]中每個元素的出現(xiàn)次數(shù)(s[a[i]]++)

4.在遍歷中，若a[i]重復(fù)則右移j，將a[j]減一（a[i]出現(xiàn)次數(shù)）。同時先減后移動j指針來避免不必要的比較。

出現(xiàn)重復(fù)的情況：

將j指針后移，且先減次數(shù)在后移指針。1，5，2因?yàn)橐呀?jīng)不在正在比較中的子序列中，它們的出現(xiàn)次數(shù)依次減去一。

最后將已有的最優(yōu)解和i-j+1比較，取長的那條為新的最優(yōu)解。

無語，一開始竟然沒有明白。

夕弦的圖片由NovalAI生成。