双指针算法

贡献者：有机物

　　双指针算法的作用类似于前缀和算法，双指针算法是运用某些单调的性质，从而优化时间复杂度。

　　双指针算法有两大类：

　　第一类是有两个序列，第一个指针指向第一个序列，另一个指针指向另一个。归并排序算法在合并的一步也是双指针算法。第二类是两个指针指向同一个序列，一般情况是一个指针指向第一个元素，另一个指向最后一个元素，维护一段区间。例子：快速排序。

　　双指针算法的时间复杂度通常为： $O (n)$ ，框架：

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

　　例 $1$ ：有一段区间中有若干单词，单词之前用一个空格隔开，要求输出每个单词，一个单词占一行。

　　做法：用 $i$ 指针枚举每个字母， $j$ 指针用于维护序列，如果不是字母就往右移动一格，当循环结束的时候， $j$ 指针的位置就在空格处，然后输出 $[i \sim j]$ 之间的字母，最后让 $i$ 指针指向 $j$ ，最后 for 循环中的 $i$ 会自增，然后重新进行双指针算法。时间复杂度为： $O (n)$ 。

char s[1010];
cin.getline(s, 1010);
int n = strlen(s);

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

    for (int k = i; k < j; k ++ ) cout << s[k];
    cout << endl;

    i = j;
}

　　例 $2$ ：给定一个长度为 $n$ 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

　　做法：在序列中，右端点为 $i$ ，左端点为 $j$ ，枚举每一个 $i$ 当作序列的右端点，判断 $j$ 最远可以到达什么地方，使得 $[j \sim i]$ 之间没有重复元素。

　　模拟一下双指针的过程：

序列：1 2 2 3 5

最开始：i = 1, j = 1

i = 2, j = 1

第三次循环，有重复元素了，i = 2, j = 2

i = 3, j = 2

i = 5, j = 2

　　每次 $i$ 往右走， $j$ 也一定会往后走，一定不会往前走，所以具有单调性，因此可以用双指针。

　　证明：

　　假设 $i$ 往后移动了 $1$ 格到达 $i^{'}$ ，那么旧的 $j$ 也一定会往右走，如果说新的 $i^{'}$ 指针对应的新的 $j^{'}$ 指针往左走了，就矛盾了。因为如果新的 $i^{'}$ 和新的 $j^{'}$ 之前没有重复元素的话，那么新的 $j^{'}$ 和旧的 $i$ 之前也一定没有重复元素，所以就矛盾了。所以 $j$ 指针具有单调性，所以只用枚举 $i$ 就行了，每次看一下 $j$ 要不要往后走。

　　证毕。

　　伪代码：

for (int i = 0, j = 0; i < n; i ++ )
{
    // check(j, i) 判断 j ~ i 之前有没有重复元素，右的话 j 就往左（后）走
    while (j < n && check(j, i)) j ++ ;    
    res = max(res, i - j + 1);
}

　　具体思路与分析：

　　指针 $i$ 对应的指针 $j$ ，表示 $j$ 离 $i$ 最远可以到达什么地方，使得 $[j \sim i]$ 之前没有重复元素。

　　对于每一个 $i$ ，因为 $[j \sim i - 1]$ 之前没有重复元素，并且是上一层循环的最优解，又因为 $a_{i}$ 中的每个数的出现次数是依次加的，所以重复元素必定是 $a_{i}$ ，所以 $j$ 肯定是往右走，减少 $a_{i}$ 出现的次数直到没有重复元素，一定不可能往左走从而增加元素，前面证明过了。

　　用一个 cnt 数组记录每个数出现的次数，如果 cnt[a[i]] > 1 说明 $a_{i}$ 重复出现了，所以 $j$ 开始往右走，并且将 $a_{j}$ 这个数出现的次数减 $1$ ，注意要先减少次数， $j$ 再往右移动。直到没有重复元素，即 $j$ 走到离 $i$ 可以到达的最远位置，然后每次更新 res。

　　 $i$ 指针和 $j$ 指针最多走 $n$ 步，所以一共最多走 $2 \times n$ 步。所以时间复杂度为 $O (n)$ 。

const int N = 100010;
int n, a[N];
unordered_map<int, int> cnt;

int main() 
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        cnt[a[i]] ++;
        while (cnt[a[i]] > 1)
        {
            cnt[a[j]] -- ;
            j ++ ;
        }

        res = max(res, i - j + 1);
    }

    cout << res << endl;
}

　　例 $3$ ：

　　给定两个升序排序的有序数组 $A$ 和 $B$ ，以及一个目标值 $x$ 。数组下标从 $0$ 开始。请你求出满足 $A [i] + B [j] = x$ 的数对 $(i, j)$ 。

　　朴素做法，暴力枚举，时间复杂度： $O (n \times m)$ 。

for (int i = 0; i < n; i ++ )   
    for (int j = 0; j < m; j ++ )
        if (a[i] + b[j] == x)
        {
            cout << i << ' ' << j << endl; 
            break;
        }

　　题目中的一个重要性质： $a$ 数组和 $b$ 数组都是单调上升的。因此 $i$ 枚举 $a$ 数组的每一位， $j$ 从 $b$ 数组的最后一位开始枚举，使得满足 a_i + b_j >= x，并且 $j$ 最小。为什么 $j$ 一定往左走？

　　证明：因为 $a$ 数组和 $b$ 数组都是单调上升的。每次找到 $j$ ，为了尽可能的达到 a_i + b_j == x，所以 $j$ 只能往左走。

　　时间复杂度： $O (n + m)$ 。

const int N = 1e5 + 10;
int a[N], b[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) cin >> b[i];
    
    for (int i = 0, j = m - 1; i < n; i ++ )
    {
        while (j > 0 && a[i] + b[j] > x) j -- ;
        if (a[i] + b[j] == x) cout << i << ' ' << j << endl;
    }
    
    return 0;
}

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。