双指针
双指针
在所求的的区间信息具有单调性的情况下(比如,区间越长,越符合要求),可以用双指针做到均摊
例如:
给定长度为
考虑直接枚举右端点
每次向右移动右端点时,将 a[r]
加入区间和,如果区间和大于等于 k
,则将左端点移除
cpp
int l=1;
int sum=0,ans=0;
for(int r=1;r<=n;++r)
{
sum+=a[r];
while(sum>=k)
{
sum-=a[l];
++l;
}
ans=max(ans,r-l+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
如果是在区间和大于
cpp
int sum=0,ans=n;
int r=0;
for(int l=1;l<=n;++l)
{
while(sum<=k&&r+1<=n)
{
++r;
sum+=a[r];
}
if(sum>k) ans=min(ans,r-l+1);
sum-=a[l];
++l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
因为信息具有单调性,所以一般也可以用二分来解决,但是双指针的均摊复杂度更优秀。