基础算法5——双指针

双指针算法

双指针是一种编程思想，不是某种具体的编程套路或是算法。很多需要双重暴力循环解决的问题，用双指针的思想都可以大大减少复杂度。

for (i = 0, j = 0; i < n; i ++)
{
    while (j < i && check(i, j)) j ++;
    
    // 每道题目的具体逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

双指针算法的核心思想是把利用某些单调的性质，把下面这种朴素算法进行优化：

for (int i = 0; i < n; i ++){
	for (int j = 0; j < n; j ++)
	   // xxxx
}

暴力穷举的复杂度是 O ( n 2 ) O(n^2) O(n2)，而双指针算法两个指针移动的总次数最多是 2 n 2n 2n，所以复杂度是 O ( n ) O(n) O(n)。

举个最简单的例子：输入一行字符串，每个单词之间用一个空格隔开，现在要求把每个单词单行输出：

#include <iostream>
#include "cstring"
using namespace  std;

int main(){
    char str[101];

    cin.getline(str, 100);

    for (int i = 0, len = strlen(str); i < len; i ++){
        int j = i;
        while (j < len && str[j]!=' ') j ++;

        // 问题的具体逻辑
        for (int k = i; k < j; k ++) cout << str[k];
        cout << endl;
        i = j;  // for 语句里还会i ++
    }

    return 0;
}
// 输入：
abc 123 jjh
// 输出：
abc
123
jjh