双指针算法

多种双指针算法：

• 分别指向两个序列：归并排序
• 在同一个序列中分别指向左右端点：快速排序（往往维护一个区间）

维护：保证区间内部一直符合某种性质

写法：

for (int i = 0, j = 0; i < n; i ++) {
    while (j < i && check(i, j)) {
        j ++;
    }
    // 具体逻辑
}

双指针算法的核心用途：优化时间复杂度，往往可以将 $O(n^2)$ 的时间复杂度优化到线性复杂度 $O(2n)$。

例题：输入一个字符串，将其中的单词输出出来，其中单词由空格隔开。

#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 ++;
        } // j 会走到单词末尾的空格处，此时 str[i, j - 1] 就是单词
        for (int k = i; k < j; k ++) {
            cout << str[k];
        }
        cout << endl;
        i = j; // 跳过整个区间
    }
    return 0;
}

最长连续不重复子序列

AC799. 最长连续不重复子序列

先考虑暴力做法：

• 枚举连续序列的起点和终点
• 判断 [j, i] 区间内是否有重复元素
• 更新长度的最大值

时间复杂度显然是 $O(n^2)$。

如何优化？本质上是寻找 i, j 之间的规律。

• [j, i] 分别代表当前最长无重复子序列的左右端点
• i 作为右端点，一定会跑满 [0, n - 1]
• j 作为左端点，每当 i 向右移动一位，j 只会从当前位置 向右移动而不会向左移动
• 如果 j 向左移动了，说明上一个序列不是最长的，矛盾！

由于 j 只会向右移动而不会向左移动，因此都只走了一遍序列，复杂度为 $O(2n)$。

至于如何判断 [j, i] 中是否有重复元素：

• 如果有，则一定是新加入的 a[i] 导致的
• 用 s[a[i]] 存储 a[i] 在当前序列中的 出现次数，如果 s[a[i]] > 1 说明重复
• 此时需要将 j 指针右移，同时 s[a[j]] --，继续维护 s 数组
• 直到 s[a[i]] == 1 时停下，说明刚刚踢出了 a[j] == a[i] 的数

核心代码：

// ...
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++) {
        s[a[i]] ++;

        while (s[a[i]] > 1) {
            s[a[j]] --;
            j ++;
        }
        
        res = max(res, i - j + 1);
    }

也可以用哈希表来做。

数组元素的目标和

AC800. 数组元素的目标和

暴力做法：$O(n^2)$

for (int i = 0; i < n; i ++) {
    for (int j = 0; j < m; j ++) {
        if (a[i] + b[j] == x) {
            return {i, j};
        }
    }
}

思考双指针中，当一个指针移动时，另一个指针是否具有某种单调性。

• 设 j 是满足 a[i] + b[j] >= x 中的最小的 j（最靠左边的）
• 当 i 从左往右移动时，a[i] 增大，因此 b[j] 要么不变，要么减小
• 因此 j 只能不变或者左移（才能保证 j 的最小性）
• j 开始时指向最右侧
• 时间复杂度：由于 i 只移动 $n$ 次，j 只移动 $m$ 次，因此为 $O(n+m)$

for (int i = 0; i < n; i ++) {
    while (j >= 0 && a[i] + b[j] > x) {
        j --;
    }
}

判断子序列

AC2816. 判断子序列