一、算法描述
含義
-
雙指針，指的是在遍歷對象的過程中，不是普通的使用單個指針進行訪問，而是使用兩個相同方向（快慢指針）或者相反方向（對撞指針）的指針進行掃描，從而達到相應的目的。
-
另外還可以根據(jù)序列進行區(qū)分，例如在快排中，雙指針指向的是同一個序列，而歸并排序中兩個指針指向的是兩個不同的序列。
怎么用
-
沒有必要對概念區(qū)分的很清楚，只需要知道怎么使用即可。
-
首先想暴力解法，然后在暴力解法的基礎(chǔ)之上，發(fā)現(xiàn)性質(zhì)，進行優(yōu)化。
-
通過題目來理解什么是雙指針吧。
二、題目描述
給定一個長度為 \(n\) 的整數(shù)序列，請找出最長的不包含重復的數(shù)的連續(xù)區(qū)間，輸出它的長度。
輸入格式
第一行包含整數(shù) \(n\)。
第二行包含 \(n\) 個整數(shù)（均在 \(0\) ~ \(10 ^ 5\) 范圍內(nèi)），表示整數(shù)序列。
輸出格式
共一行，包含一個整數(shù)，表示最長的不包含重復的數(shù)的連續(xù)區(qū)間的長度。
數(shù)據(jù)范圍
\(1 ≤ n ≤ 10 ^ 5\)
輸入樣例：
5
1 2 2 3 5
輸出樣例：
3
三、題目來源
四、算法思路
-
首先暴力做法就是，枚舉左端點 \(l\) ，枚舉右端點 \(r\) ，然后枚舉區(qū)間 \([l, r]\) 判斷是否有重復數(shù)字，然后更新答案，顯然該做法時間復雜度會非常高，所以可以優(yōu)化一下。
-
如何優(yōu)化呢？
-
遍歷數(shù)組 \(a\) 中的每一個元素 \(a[i]\) , 對于每一個\(i\)，找到j使得雙指針 \([j, i]\) 維護的是以 \(a[i]\) 結(jié)尾的最長連續(xù)不重復子序列，長度為 \(i - j + 1\) , 將這一長度與 \(res\) 的較大者更新給\(res\)。文章來源：http://www.zghlxwxcb.cn/news/detail-746829.html
-
對于每一個 \(i\) ，如何確定j的位置：由于 \([j, i - 1]\) 是前一步得到的最長連續(xù)不重復子序列，所以如果 \([j, i]\) 中有重復元素，一定是 \(a[i]\)，因此右移 \(j\)直到 \(a[i]\) 不重復為止（由于 \([j, i - 1]\) 已經(jīng)是前一步的最優(yōu)解，此時 \(j\) 只可能右移以剔除重復元素 \(a[i]\)，不可能左移增加元素，因此， \(j\) 具有“單調(diào)性”、本題可用雙指針降低復雜度）。文章來源地址http://www.zghlxwxcb.cn/news/detail-746829.html
五、源代碼
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N], s[N];
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int res = 0;
for (int i = 0, j = 0; i < n; ++i)
{
++ s[a[i]];
while (j <= i && s[a[i]] > 1)
{
-- s[a[j]];
++ j;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
到了這里，關(guān)于最長連續(xù)不重復子序列（雙指針）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
