雙指針 最長連續不重複子序列

雙指針

雙指針嚴格來講，算不上不一種算法，應該稱為一種技巧。

它的作用是通過巧妙地轉換，将樸素地多重循環，轉為雙指針，進而把時間複雜度從O(n^2)降到O(n)

雙指針的一貫做法

1. 先考慮最樸素的做法
2. 考慮将樸素做法優化到雙指針

最長連續不重複子序列

最長連續不重複子序列

思路

1. 樸素思路——雙重循環

2. 存在性質：一個不重複序列的子序列也一定是不重複序列

   是以，隻需要對數組周遊作為右端點，如出現重複數字，則左端點回退。

代碼

#include<iostream>
#include<set>
#include<algorithm>
#define max(x,y) ((x)>(y)?(x):(y))

using namespace std;

set<int> st;
int num[100010];//數列中每個數的出現次數
int a[100010]; //讀取的數列
int res = -1;

int main()
{
	int n;
	cin >> n;
	for(int i=0;i<n;i++) {
		cin >> a[i];
	}
	for(int i=0,j=0;i<n;i++) {
		num[a[i]] ++;
		while(num[a[i]] > 1) {//出現重複數
			num[a[j]] --;//重複數以及序列中位置在其左邊的數，出現次數減一
			j ++;//“目前不重複序列左端點右移
		}
		res = max(res,i-j+1);
	}
	cout << res;
	
	return 0;
}