算法 - 双指针算法

2020-08-05 10:11:32

双指针算法是从暴力中优化，根据题目要求的某种性质进行优化。快排， 归排都用了双指针算法。把具有某种性质给提出来。简化时间复杂度的方法。

比如这样一道题目：

给定一些字符串，中间以空格隔开，输出每个字符串。

1
2
3
4
5
6
7
8
for(int i = 0, j = 0; i < n; i++)
{
    j = i;
    while(j < n && s[j] != ' ') j++;

    for(int k = i; k <= j; k++) printf("%s", s[k]);
    i = j;
}

一些C++的字符串读取操作：
fgets(char数组, 最大读取长度, stdin)
scanf()会读取到字符串为空，或者回车的情况。

所以双指针，统一可以写成这样模板：

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

    // 具体题目逻辑
}

最长连续不重复子序列， 来源：

https://www.acwing.com/problem/content/801/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int q[N], s[N];
int n;

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


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

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

    cout << res << endl;
    return 0;
}

数组元素的目标和:

https://www.acwing.com/problem/content/802/

因为数组具有单调性，可以由一下组成：

  • a[i] + b[j] > x j–
  • 否则i++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>

using namespace std;


const int N = 100010;
int n, m, x;
int a[N], b[N];

int main()
{
    cin >> n >> m >> x;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i++) scanf("%d", &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;
            break;
        }
    }
    return 0;
}