双指针算法的应用有很多种,如排序,kmp等。
双指针有两种,一种是两个指针各指向一个序列,另一种是两个指针指向同一个序列。
对于后者而言,有朴素算法(暴力写法):
for(i=0;i<n;i++){
for(j=0;j<n;j++){
...
}
}
而通过以下模板,可以将这种时间复杂度为$O(n^2)$的算法优化到$O(n)$:
for(i=0;i<n;i++){
while(j<n&&check(i,j)){j++;}
...//每道题的具体逻辑
}
如将一串单词逐个输出,即用到了最简单的双指针算法:
#include<iostream>
#include<cstring>
using namespace std;
int main(){
char ch[100];
cin.getline(ch,100);
int n=strlen(ch);
for(int i=0;i<n;i++){
int j=i;
while(j<n&&ch[j]!=' '){j++;}
for(int k=i;k<j;k++){cout<<ch[k];}
cout<<'\n';
i=j;
}
return 0;
}
此例将一个指针放在单词首字母,另一个指针通过平移指向单词末尾。
在优化之前,可以先行思考朴素做法。
双指针算法可以减少一些不必要的枚举,从而加快运行速度。
咱们省赛第一题就是这个双指针hh
现在终于知道为啥Time Limit Exceeded了T_T