双指针算法

                     

贡献者: 有机物

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

   双指针算法有两大类:

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

   双指针算法的时间复杂度通常为:$\mathcal{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$ 会自增,然后重新进行双指针算法。时间复杂度为:$\mathcal{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$ 步。所以时间复杂度为 $\mathcal{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)$。

   朴素做法,暴力枚举,时间复杂度:$\mathcal{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$ 只能往左走。

   时间复杂度:$\mathcal{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;
}

                     

© 小时科技 保留一切权利