双指针维护笔记

双指针特指两个指针共同维护一个数组：
从两端分别维护，从同一端点交叉维护

从两端分别维护：

例：快速排序，（从小到大排序）

在快速排序中，我们安排了两个指针从需要排序的数组的左右两端开始向中间移动

更新方式是，当 $i$ 指针从左向右移动，$j$ 指针从右向左移动时，若 $i$ 的值大于 $j$ 的值

则交换 $i,j$ 两个指针各自指向的值，继续向中间逼近，直到 $i,j$ 相遇

从同一端点交叉维护：

例：输入 $n$ 个单词，用空格隔开，输出每行一个单词

我们令有 $i,j$ 两个指针，一开始都指向字符串组的 char[0]

首先固定一个指针 $j$ ，指针 $i$ 开始向右移动

更新方式是，当 $i$ 指针指向的值为 ‘ ‘ (空格)时，两个指针中间的char段则为第一个单词

然后将 $j$ 同步到 $i$ 的位置并向右移动一个单位，使得 $j$ 指向下一个单词的首字母，继续执行 $i$ 向右移动的操作

双指针算法可以将时间复杂度 $O(n^2)$ 优化至 $O(n)$

//朴素算法
for (int i=0;i<n,i++){
    for (int j=0;j<n;j++){
        if (check(j,i))
        ......
    }
}
//双指针算法
for (int i=0;i<n;i++){
    while (j<=i&&check(j,i)){
        ......
    }
}