本笔记内容来源于算法基础课

双指针

种类

1. 一个指针位于一个序列，另一个指针位于另一个序列。例：归并排序
2. 两个指针位于同一个序列。例：快速排序

基本模板

枚举以j开始i结束的区间

for (i = 0, j = 0; i < n; i++) {
    while(j < i && check(i, j)) j++;
    // 1. 保证不越界 2. 满足某种性质，不断向后移动j
    ......
}

枚举以i开始j结束的区间

for (i = 0; i < n; i++) {
    int j = i;
    while (j < n && check(i, j)) j++;
    if (j > i) i = j - 1; // 注意因为i最后会执行i++,因此i应当移动到j-1
}

注意if (j > i)避免当j == i时，加一减一抵消，i无法移动，而造成死循环

核心思想：

使用暴力做法，时间复杂度为$O(n^2)$

for(int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        ......

使用双指针算法，由于每个指针都是向后移动而不会向前，因此时间复杂度为$O(2n) = O(n)$

因此观察单调性，即对于给定的i j，当i++后，

1. j向某个方向移动，直到满足某个性质
2. 当满足某个性质后，j向某个方向移动

注意i j可能互换

因此核心思想为，运用单调性将$O(n^2)$优化到$O(n)$

例题

输入由空格隔开的由单词构成的字符串，输出每个单词
使用双指针维护一个区间范围
i指向单词的开头，j指向单词的末尾

for (int i = 0; i < n; i++) {
    int j = i;
    while (j < n && str[j] != ' ') j++;
    ......
    i = j
}

注意是此类双指针与模板不同，枚举i开始j结束的区间，但由于指针的赋值，使得时间复杂度仍然是$O(n)$

对于给定的有序数组，去除重复元素

int j = 0;
for (int i = 0; i < n; i++) {
    if (i == 0 || a[i] != a[i - 1]) 
        a[j++] =  a[i];
}

j指向重复的元素的第一个元素，因此只有当为第一个元素和前一个元素不相等时才向后移动 Leetcode 26

Leetcode 83

Acwing 799 采用指针j不断移动
Acwing 800 注意移动方向
Acwing 3973 位于两个数组中的相邻元素