【算法基础】双指针

博主： Fivk
发布时间：2022 年 01 月 02 日
1406 次浏览
2627字数
分类：算法基础

# 双指针算法有两类：

1. 两个指针分别指向不同的序列（归并排序），属于**对撞指针**
2. 两个指针指向同一个序列（快排），属于**快慢指针**

# 模板

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

# 特点

所有双指针算法时间复杂度都是$O(n)$，将朴素算法优化到$O(n)$。
</div>

# 例题

## 1.输出单个字符

给定一行字符串，对字符串进行切分。

#### 输入格式

一行字符串

#### 输出格式

多行字符串

#### 输入样例

```in
aaa bbb ccc
```

#### 输出样例

```out
aaa
bbb
ccc
```

```cpp
#include <iostream>
#include <string.h>
using namespace std;

int main() {
    char str[1001];
    cin.getline(str,1001);
    int n = strlen(str);
    for (int i = 0; str[i]; i++) {
        int j = i;
        while(j < n && str[j]!= ' ') j++;
  
        // 这道问题的具体逻辑
        for (int k = i ; k < j; k++)
        cout << str[k];
        cout << endl;
        i = j;
    }
    return 0;
}
```

## 2.最长连续不重复子序列

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

#### 输入格式

第一行包含整数 **n**。

第二行包含 **n** 个整数（均在 0~100000 范围内），表示整数序列。

#### 输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

#### 数据范围

1≤n≤105

#### 输入样例：

```
5
1 2 2 3 5
```

#### 输出样例：

```
3
```

朴素做法：

```cpp
for (int i = 0; i < n; i++)
    for (int j = 0; j <= i; j++)
        if (check(j, i)) {
		res = max(res,i - j + i);
	}
```

双指针做法：

```cpp
for (int i = 0, j = 0; i < n; i++) {
    while(j <= i && check(i,j)) j++;
    res = max(res, i - j + 1);
}
```

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
int a[N];
int s[N];

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++) {
		s[a[i]]++;
		while(s[a[i]] > 1) {
			s[a[j]]--;
			j++;
		}
		res = max(res, i - j + 1);
	}
	cout << res;
	return 0;
}
```

## 3.数组元素的目标和

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x 的数对 (i,j)。

数据保证有唯一解。

#### 输入格式

第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。

第二行包含 n 个整数，表示数组 A。

第三行包含 m 个整数，表示数组 B。

#### 输出格式

共一行，包含两个整数 i 和 j。

#### 数据范围

数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109

#### 输入样例：

```
4 5 6
1 2 4 7
3 4 6 8 9
```

#### 输出样例：

```
1 1
```

双指针主要先通过暴力算法中找到单调性，比如这两个数组都是单调递增，我们可以用`i`指向第一个数组的头，使用`j`指向第二个数组的尾部，遍历第一个数组时，如果`a[i] + b[j] > x`，则`j`只能时递减的，这就构造了一个单调性。

(双指针) `O(n)`

`i`从 `0`开始 从前往后遍历

`j`从 `m - 1`开始 从后向前遍历

和纯暴力的`O(n2)` 算法的区别就在于

> `j`指针不会回退

![](https://blog.fivk.cn/usr/uploads/2022/01/1044051575.png)

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int a[N];
int b[N];
int m, n, x;

int main() {
	scanf("%d %d %d",&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) {
			printf("%d %d", i, j);
			break;
		}
	}

return 0;
}
```

## 4.判断子序列

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按**原有次序排列** 而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

#### 输入格式

第一行包含两个整数 n,m。

第二行包含 n 个整数，表示 a1,a2,…,an。

第三行包含 m 个整数，表示 b1,b2,…,bm。

#### 输出格式

如果 a 序列是 b 序列的子序列，输出一行 `Yes`。

否则，输出 `No`。

#### 数据范围

1≤n≤m≤105,
−109≤ai,bi≤109

#### 输入样例：

```
3 5
1 3 5
1 2 3 4 5
```

#### 输出样例：

```
Yes
```

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m, t;
int a[N];
int b[N];

int main() {
	scanf("%d %d",&n, &m);

for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	for (int j = 0; j < m; j++) scanf("%d", &b[j]);

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

if (i == n) puts("Yes");
	else puts("No");

return 0;
}
```

最后修改：2022 年 01 月 04 日

如果觉得我的文章对你有用，请随意赞赏

【算法基础】双指针

Fivk • 2022 年 01 月 02 日

# 双指针算法有两类：

1. 两个指针分别指向不同的序列（归并排序），属于**对撞指针**
2. 两个指针指向同一个序列（快排），属于**快慢指针**

# 模板

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

# 特点

所有双指针算法时间复杂度都是$O(n)$，将朴素算法优化到$O(n)$。
</div>

# 例题

## 1.输出单个字符

给定一行字符串，对字符串进行切分。

#### 输入格式

一行字符串

#### 输出格式

多行字符串

#### 输入样例

```in
aaa bbb ccc
```

#### 输出样例

```out
aaa
bbb
ccc
```

```cpp
#include <iostream>
#include <string.h>
using namespace std;

## 2.最长连续不重复子序列

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

#### 输入格式

第一行包含整数 **n**。

第二行包含 **n** 个整数（均在 0~100000 范围内），表示整数序列。

#### 输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

#### 数据范围

1≤n≤105

#### 输入样例：

```
5
1 2 2 3 5
```

#### 输出样例：

```
3
```

朴素做法：

```cpp
for (int i = 0; i < n; i++)
    for (int j = 0; j <= i; j++)
        if (check(j, i)) {
		res = max(res,i - j + i);
	}
```

双指针做法：

```cpp
for (int i = 0, j = 0; i < n; i++) {
    while(j <= i && check(i,j)) j++;
    res = max(res, i - j + 1);
}
```

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
int a[N];
int s[N];

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++) {
		s[a[i]]++;
		while(s[a[i]] > 1) {
			s[a[j]]--;
			j++;
		}
		res = max(res, i - j + 1);
	}
	cout << res;
	return 0;
}
```

## 3.数组元素的目标和

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x 的数对 (i,j)。

数据保证有唯一解。

#### 输入格式

第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。

第二行包含 n 个整数，表示数组 A。

第三行包含 m 个整数，表示数组 B。

#### 输出格式

共一行，包含两个整数 i 和 j。

#### 数据范围

数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109

#### 输入样例：

```
4 5 6
1 2 4 7
3 4 6 8 9
```

#### 输出样例：

```
1 1
```

(双指针) `O(n)`

`i`从 `0`开始 从前往后遍历

`j`从 `m - 1`开始 从后向前遍历

和纯暴力的`O(n2)` 算法的区别就在于

> `j`指针不会回退

![](https://blog.fivk.cn/usr/uploads/2022/01/1044051575.png)

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int a[N];
int b[N];
int m, n, x;

int main() {
	scanf("%d %d %d",&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) {
			printf("%d %d", i, j);
			break;
		}
	}

return 0;
}
```

## 4.判断子序列

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按**原有次序排列** 而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

#### 输入格式

第一行包含两个整数 n,m。

第二行包含 n 个整数，表示 a1,a2,…,an。

第三行包含 m 个整数，表示 b1,b2,…,bm。

#### 输出格式

如果 a 序列是 b 序列的子序列，输出一行 `Yes`。

否则，输出 `No`。

#### 数据范围

1≤n≤m≤105,
−109≤ai,bi≤109

#### 输入样例：

```
3 5
1 3 5
1 2 3 4 5
```

#### 输出样例：

```
Yes
```

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m, t;
int a[N];
int b[N];

int main() {
	scanf("%d %d",&n, &m);

for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	for (int j = 0; j < m; j++) scanf("%d", &b[j]);

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

if (i == n) puts("Yes");
	else puts("No");

return 0;
}
```

【算法基础】双指针

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【C】文件_文件的格式化操作(fscanf，fprintf)

【Linux】Linux-Day02

【踩坑日志】Controller中使用service执行方法，一直提示NULL

【C++】STL常用容器_stack容器

【开发技巧】@CrossOrigin注解解决跨域问题

【算法基础】双指针