一 双指针算法

我们用归并排序合并两个有序序列时，就是使用的双指针算法

将两个指针每次移动一下，排序过程就结束了

双指针算法有很多种

第一种：两个指针，一个指针指向一个序列，第二个指针指向第二个序列

第二种（用的更多）：指向一个序列，类似于快排，一个指针只向开头，另一个指针指向结尾，两个指针维护的是一段区间

双指针算法的通用模板：

for(int i=0,j=0;i<n;i++){
    while(j<i && check(i,j))j++;
    //检查j是否在合法的范围内，并且i,j满足某种性质
   //每道题目的具体逻辑
}

核心思想

暴力写法

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    //复杂度O(n*n)
   }
}

双指针算法复杂度是 $O(n)$

就是把朴素算法优化到 $O(n)$

输入一个字符串，把他的单词输出出来：

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[1000];
    fgets(s,sizeof s,stdin);
    int a=strlen(s);
    for(int i=0;i<a;i++){
        int j=i;
        while(j<a && s[j]!=' ')j++;
        for(int k=i;k<j;k++){
            cout<<s[k]<<endl;
        }
        i=j;
    }
    return 0;
}