双指针

模板

对于一个序列 借助两个指针维护一个区间(i与j有单调关系)

for(int i=0;i<n;i++){
    j=i;
    while(j<n&&check(i,j)){
        j++;
    }
    //每道题的具体逻辑
}

可将暴力两层嵌套循环O(n^2)优化到O(n)

799. 最长连续不重复子序列

找出最长的不包含重复数字的连续子序列[l,c]的长度
input 1 2 2 3 5
output 3

int res=0;
for(int r=0,l=0;r<n;r++){
	cnt[a[r]]++;//计时器的作用
	while(l<r&&s[a[r]]>1){//当出现重复的数字j向前移动一位直到不再重复
		cnt[a[l]]--;
		l++;	
	}
	res=max(res,r-l+1);
}

实现unique函数

vector<int>::iterator unique(vector<int> &a){
	int j=0;
	for(int i=0;i<a.size();i++){
		if(!i||a[i]!=a[i-1]){//第一个或满足不与前一个数相同 
			a[j]=a[i];
			j++;
		}
	}
	return a.begin()+j;//返回值必须是迭代器
}

调用实现去重操作

sort(a.begin(),a.end());
a.erase(unique(a),a.end());