跳转至

双指针算法⚓︎

类型⚓︎

常见问题分类：

  • 一个数组两个指针：对于一个序列，用两个指针维护一段区间，如快速排序
  • 两个数组各一个指针：对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

核心思想：将算法时间复杂度从朴素算法的 \(O(n^2)\) 降低到 \(O(n)\)

1
2
3
4
5
for (int i = 0, j = 0; i < n; i++) {
    while (j < i && check(i, j)) j++;

    //每道题目的具体逻辑
}

例题：输出字符串 例题：数组元素的目标和 注意要寻找单调性

范例：最长连续不重复子序列⚓︎

例题：最长连续不重复子序列

  • 遍历数组a中的每一个元素a[i], 对于每一个i，找到j使得双指针[j, i]维护的是以a[i]结尾的最长连续不重复子序列，长度为i - j + 1, 将这一长度与res的较大者更新给res。
  • 对于每一个i，如何确定j的位置：由于[j, i - 1]是前一步得到的最长连续不重复子序列，所以如果[j, i]中有重复元素，一定是a[i]，因此右移j直到a[i]不重复为止(由于[j, i - 1]已经是前一步的最优解，此时j只可能右移以剔除重复元素a[i]，不可能左移增加元素，因此，j具有“单调性”、本题可用双指针降低复杂度)。
  • 用数组s记录子序列a[j ~ i]中各元素出现次数，遍历过程中对于每一个i有四步操作：cin元素a[i] -> 将a[i]出现次数s[a[i]]加1 -> 若a[i]重复则右移j（s[a[j]]要减1） -> 确定j及更新当前长度i - j + 1给res。

注：当数据范围很大时，可以用哈希表做。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# include <iostream>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main() {
    int n, res = 0;
    cin >> n;
    for (int i = 0, j = 0; i < n; ++ i) {
        cin >> a[i];
        ++s[a[i]];
        // 当a[i]重复时，先把a[j]次数减1，再右移j。
        while (s[a[i]] > 1) --s[a[j++]];
        res = max(r, i - j + 1);
    }
    cout << res << endl;
    return 0;
}