蓝桥杯专项复习——双指针

目录

双指针算法：双指针算法-CSDN博客

最长连续不重复子序列

 P8783 [蓝桥杯 2022 省 B] 统计子矩阵

---

双指针优化思路：当存在重复枚举时，可以考虑是否能使用双指针进行优化

双指针算法：双指针算法-CSDN博客

最长连续不重复子序列

注意理解题目：这里的连续区间是指没有重复数字的区间，不是没有重复数字并且数字大小连续的区间，即1，2，5就是一个没有重复数字的连续区间

思路：

 可以直接遍历，但是时间会是O(n^2)级别，

即假设有一个区间1，2，3，1，首先对于1进行枚举，当遍历到最后一个1时结束，再进行下一个枚举即从2开始向后枚举，此时2,3被枚举了两次，即进行了重复枚举，可以在这里进行优化

使用双指针进行优化
前面的指针表示当前的位置，后面的指针表示当前数字能够达到的位置

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=100000+10;int n;
int a[N];
int mx;signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//使用双指针算法进行优化 int j=1; //慢指针 map<int,int> mp;//使用 一个桶来判断是否有重复的数字 for(int i=1;i<=n;i++)//快指针 {while(j<=n&&mp[a[j]]==0)//当mp[a[j]]==1时表示出现重复数字 {mp[a[j]]++;j++;}//while循环结束后j会多加一次，所以满足条件的长度为j-i不用+1mx=max(mx,j-i); mp[a[i]]--;//取消标记，为下一次遍历做准备 }cout<<mx<<endl;return 0;
}

 P8783 [蓝桥杯 2022 省 B] 统计子矩阵

二维前缀和+双指针的优化

如果直接暴力枚举是O(n^4)不能过
由分析可知中间有些地方是会重复枚举，这时可以使用双指针进行优化
设置两个指针，当j指针所在位置的和大于k时移动i，让其和小于k
先列出所有的行n^2，再通过双指针对所有的列进行移动2m，最终是n^3级别

 

#include<bits/stdc++.h>
#define int long long 
using namespace std;const int N=1000+10;int pre[N][N],g[N][N];
int n,m,k;
int ans;int ptr(int x1,int y1,int x2,int y2)
{return pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1];
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>g[i][j];pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+g[i][j];//预处理前缀和 }for(int i=1;i<=n;i++){for(int j=i;j<=n;j++)//j要从i开始 ,到n结束 {for(int l=1,r=1;l<=m;l++)//双指针遍历{while(r<=m&&ptr(i,l,j,r)<=k) r++;ans+=r-l;}}}cout<<ans<<endl;return 0;
}