双指针算法

• 第一类：指向的是两个序列，例如：归并排序中的双指针

• 第二类：指向的是一个序列（常见），例如：快速排序的双指针

1. 核心思想

将下面的朴素算法的时间复杂度优化到 \(O(n)\)

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        // 操作

为什么双指针算法的时间复杂度是 \(O(n)\) ?

双指针算法的时间复杂度为 \(O(n)\) 的原因是，它通常在一个循环中使用两个指针进行迭代，而这两个指针相对于输入规模 \(n\) 的数量级是线性的。

在双指针算法中，指针通常从输入序列的两端开始，然后向中间移动，根据特定的条件调整指针的位置。算法的终止条件可能是两个指针相遇或到达特定位置。

由于每次迭代中，指针的移动都是以固定的步长进行的，而且指针从两个方向同时移动，因此整个算法的执行时间与输入规模 \(n\) 成线性关系。换句话说，算法的运行时间随着输入规模的增加而线性增长。

需要注意的是，虽然双指针算法的时间复杂度通常是 \(O(n)\)，但也可以有特殊情况下的变体，其时间复杂度可能是 \(O(n^2)\) 或其他不同的复杂度。这取决于算法的具体实现和问题的特定要求。但是，一般而言，双指针算法的时间复杂度是线性的，即 \(O(n)\)。

2. 例子

题目要求：

输入一个字符串，其中包含多个单词，每个单词用空格隔开，输出每个单词。（假定字符串开始时没有空格，且每个单词之间只有一个空格）

分析：

代码：

#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    char str[1000];
    gets(str);
    int n = strlen(str);
    for (int i = 0; i < n; i++)
    {
        int j = i;
        while (j < n && str[j] != ' ') j++;
        // 这道题的具体逻辑
        for (int k = i; k < j; k++) cout << str[k];
        cout << endl;
        i = j;
    }
    return 0;
}

3. 模板

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

总结（双指针算法的实现思路）

1. 写出题目对应的暴力解法（时间复杂度为 \(O(n^2)\)），寻找两个循环索引 \(i、j\) 之间的单调关系
2. 如果有单调关系的话，利用其单调关系，把状态数量由 \(n^2\) 变成 \(n\)，从而把时间复杂度由 \(O(n^2)\) 变成 \(O(n)\)