双指针算法

双指针算法的核心就是依据某些性质(单调性), 将本来需要两重循环 $ O(n^{2}) $ 来枚举的优化成 $ O(2 n) $ 的, 即两个指针总共循环的次数不超过 $2n$ 次

双指针算法用处广泛, 如在快排、归并排序中使用

思考方式

先写一个暴力算法, 然后找出两个指针之间的规律(如单调性), 最终使得求解时指针不向回退, 达到优化的目的

类型

类型一, 指针指向同一个序列(如快排)

类型二, 指针指向多个序列(如归并)

基本模式

for(i = 0, j = 0; i < n; i++) {
    //check函数检查每道题目中的具体逻辑
    while(j < i && check(i, j)) j++;
}

取出字符串中的每一个单词就是一种双指针算法

指针 $i$ 循环整个字符串, 当碰到不是空格的字符时, 开指针 $j$ 来找到这个单词结束的位置, 找到后取出整个字符串, 并使得 $i = j$

双指针算法的基本认识

原文：https://www.cnblogs.com/xqxq/p/13776590.html