双指针算法
1.常见双指针算法有两个指针指向两个序列和两个指针指向一个序列.
2.算法核心思想:
从暴力算法的二重循环,利用题目的单调性质变为单次循环的双指针算法.
类似于从串行->并行.
3.常用模板
for(int i = 0, j = 0; i < n; i++)
{
while( j>0 && check(i,j) ) j++;//j的边界判断 + 单调性的判断
/*题目具体逻辑*/
}
799. 最长连续不重复子序列
解题思路
首先考虑暴力算法:
枚举所有的(i,j)对,判断a[j~i]之间是否有重复数字.
找到单调性:
假定我们维护一个无重复数字的最长区间(j~i),那么随着i的增长,j也只会增长或不变,不会减小.
反证法:假设当i->i+1时
无重复数字出现,如果此时j可以变成j' = j-1,也就是(j'~i+1)无重复数字,那么该区间应
在j'时遇到,否则不符合我们最长区间的定义.
若有重复数字出现,那么j只能增加(缩小区间直到无重复数字出现,类似于从区间去掉数字),
若j减小不符合无重复数字的定义.
双指针求解:
对于每个i,求解对应最小的j.
举例:
序列: 1 2 2 2 3 5
下标: 0 1 2 3 4 5
当 i = 0 时, s[1] == 1, j = 0;
当 i = 1 时, s[2] == 1, j = 0;
当 i = 2 时, s[2] == 2, j++判断 -> j = 2
当 i = 3 时, s[2] == 2, j++判断 -> j = 3
当 i = 4 时, s[3] == 1, j = 3
当 i = 5 时, s[5] == 1, j = 3
时间复杂度
看上去双指针算法也是双重循环,但i,j只会单调变化.(对于暴力算法,每个i内层循环j都会从0->i).
i只会增加n次,j只会增加m次.所以时间复杂度0(n+m).
C++ 代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int Max_N = 1e5 + 10;
int n;
int a[Max_N],s[Max_N];//s[i]记录数字i在当前区间出现次数.
int main()
{
scanf("%d",&n);
for( int i = 0; i < n; i++ ) scanf("%d",&a[i]);
int res = 0;
for( int i = 0, j = 0; i < n; i++ )
{
s[a[i]]++;
while( s[a[i]]>1 )//check 保证(j~i)无重复数字 且只要符合就退出 保证最长
{//这里j的边界不需要考虑 因为j==i时必然无重复数字
s[a[j]]--;
j++;
}
res = max( res, i - j + 1 );
}
printf("%d\n",res);
return 0;
}
800. 数组元素的目标和
解题思路
暴力:
枚举所有(i,j),判断a[i]==b[j].
单调性:
i从小到大扫描a,因为a,b升序,所以随着i增大a[i]增大.那么对于可能的b[j]只能减小.
(如果a[i]满足条件,b[j]=x-a[i]).也就是i增大,j减小.
双指针:
i从小到大扫描a,对应j从大到小扫描b.对于每个i找到第一个j满足a[i]+b[j]<=x.
时间复杂度
i最多加n次,j最多减m次.O(n+m)
C++ 代码
#include<cstdio>
const int Max_N = 1e5 + 10;
int n, m, x;
int a[Max_N], b[Max_N];
int main()
{
scanf("%d%d%d",&n,&m,&x);
for( int i = 0; i < n; i++ ) scanf("%d",&a[i]);
for( int j = 0; j < m; j++ ) scanf("%d",&b[j]);
for( int i = 0, j = m - 1; i < n; i++ )
{
while( j>=0 && a[i]+b[j] > x ) j--;//第一个满足a[i]+b[j]<=x的j
if( a[i]+b[j] == x )
{
printf("%d %d\n",i,j);
break;
}
}
return 0;
}
2816. 判断子序列
解题思路
单调性:
按原有次序排列而得到的序列.
双指针:
顺次扫描原序列b,当原序列值b[j]与当前a[i]相等时,i++;
按这种方法若可以找到,那么a是b的子序列.
若a是b子序列,用这种方法可以找到:证明过程用到了替换方法.详情见y总视频 - -
时间复杂度
O(n+m)
C++ 代码
#include<cstdio>
const int Max_N = 1e5 + 10;
int n, m;
int a[Max_N], b[Max_N];
int main()
{
scanf("%d%d",&n,&m);
for( int i = 0; i < n; i++ ) scanf("%d",&a[i]);
for( int i = 0; i < m; i++ ) scanf("%d",&b[i]);
int i = 0, j = 0;
while( i<n && j<m )
{
if( a[i]==b[j] )
i++;
j++;
}
if( i==n ) puts("Yes");
else puts("No");
return 0;
}