双指针.md

#最大不重复子序列

对于一段序列，现假定一段不重复子序列的起始指针与结束指针分别为j与i，那么区间长度就是i-j+1。

我们可以通过i与J两个指针对序列进行遍历从而得到最大不重复子序列长度。

![[Pasted image 20230812161425.png]]

i指针不断向右移动，与此同时每次移动都要check一次从j到i的区间是否符合条件。如果出现不符合的情况，说明新进入的元素（arr i ）与之前的元素发生了冲突（一定是arr i 而不是其他元素，否则与约定矛盾，即要求从j到i的区间一定是不重复区间），这时将j指针向右移动直到符合条件为止。每一次i向右移动就check一次，并取区间长度最大值。

要求：求出长度为n的区间中最大不重复子区间长度是多少。

799. 最长连续不重复子序列 - AcWing题库

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll arr[100005];
ll s[100005];
ll n;
int main (void)
{
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>arr[i];
	
	ll ans=0;
	for(int i=0,j=0;i<n;i++)
	{
		s[arr[i]]++;
		while(j<i&&s[arr[i]]>1)
		{
			s[arr[j]]--;
			j++;
		}
		ans=max(ans,(ll)i-j+1);
	}
	cout<<ans<<endl;
	
	return 0;
		
}

#求序列中的和

即给定两段序列，求出两个索引值，令a[i]+b[j]=所要求的的值x

800. 数组元素的目标和 - AcWing题库

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,m,x;

ll arr[100005];
ll brr[100005];

int main (void)
{
	cin>>n>>m>>x;
	for(int i=0;i<n;i++)
	cin>>arr[i];
	for(int i=0;i<m;i++)
	cin>>brr[i];
	
	int j=m-1;
	for(int i=0;i<n;i++)
	{
		while(j>=0&&arr[i]+brr[j]>x)
		j--;
		if(arr[i]+brr[j]==x)
		cout<<i<<" "<<j<<endl;
				
	}		
	return 0;
	
}

#检查是否子序列

给定两个序列，检查第一个序列是否是第二个序列的子序列

2816. 判断子序列 - AcWing题库

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,m;
ll arr[100005];
ll brr[100005];

int main (void)
{
	cin>>n>>m;
	
	for(int i=0;i<n;i++)
	cin>>arr[i];
	for(int i=0;i<m;i++)
	cin>>brr[i];
	
	ll i=0;
	ll j=0;
	while(i<n&&j<m)
	{
		if(arr[i]==brr[j])
		i++;
		j++;
	}
	if(i==n)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
	
	return 0;
		
}