双指针算法
1、分类
(1) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
(2) 对于一个序列,用两个指针维护一段区间
2、核心思想
for( int i = 0 ; i<n;i ++ )for( int j = 0 ; j < n ; j ++ )时间复杂为O(n^2)
正常做题的时候一般都会使用两个for循环来解决问题
双指针算法的作用就是为了上面的朴素算法的时间复杂度优化到O(n)
3、代码模版
for( i = 0 ,j==0 ;i<n; i ++ ){while( j < i && check(i,j) ) j ++;//每道题的具体逻辑}
4、测试题
给定一串字符,每段字符之间可能会有空格,以空格为会车点输出结果
案例:
abd des ajs
结果:
abd
des
ajs
#include <iostream>#include <string.h>using namespace std;int main(){char str[100];//读入该字符gets_s(str,100);//计算字符的长度int n = strlen(str);for (int i = 0; i < n; i++){int j = i;//该条件下,最终j的位置停留在空格的地方while (j < n && str[j] != ' ') j++;//具体逻辑for (int k = i; k < j; k++)cout << str[k];cout << endl;//赋值给i之后,i ++ 从下一个字符开始i = j;}return 0;}