双指针

⬅ 返回

1、滑动窗口

例题：

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

解法：

维护一个从j到i的窗口，里面全是不重复数。初始将i和j都设为0，指向数组起始元素。然后开始遍历数组i：0—>n，并记录每个元素出现的次数，如果此时元素c出现了第两次，则让j开始向后移，直到窗口里面只有一个元素c。

代码：

int a[N];//数组a为整数序列
int b[N];//数组b记录每个元素的出现次数 可以用hashmap
int main ()
{
    int n;cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int i,j=0;
    int res=0;//res记录最长不重复序列长度
    for(i=0;i<n;i++)
    {
		    int c = a[i];//当前遍历的元素为c
        b[c]++;//元素c的出现次数+1
        while(b[c]>1)//若元素c的次数不为1 让j++ 窗口缩小 知道窗口里面只有一个c
        {
            b[a[j]]--;//元素a[j]的数量-1
            j++;//窗口右移
        }
        res=max(res,i-j+1);//统计此时窗口大小
    }
    cout<<res;
}

2、双指针

例题

给定两个升序排序的有序数组 a和 b，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 a[i]+b[j]=x 的数对 (i,j)。

数据保证有唯一解。

解法：

由于数组a、b有序，考虑双指针：i指向a数组的第一个元素，j指向b数组的最后一个元素。

如果a[i]+b[j]>x 令j-1（指针左移）此时值太大了 要减小

如果a[i]+b[j]<x 令i+1（指针右移）此时值太小了 要增大

代码：

int a[N],b[N]; 
int main(){
	int n,m,x;cin>>n>>m>>x;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++)cin>>b[i];
	
	int i=0,j=m-1;//双指针
	while(a[i]+b[j]!=x)
	{
		if(a[i]+b[j]>x)
			j--;
		else
			i++;
	}
	cout<<i<<" "<<j<<endl;
}