您现在的位置是:首页 >其他 >双指针算法网站首页其他

双指针算法

Hongs_Cai 2024-06-14 17:17:09
简介双指针算法


一、双指针算法的概念

【核心思想】

for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++)

将像如上的朴素算法 O ( n 2 ) O(n^2) O(n2) 优化到 O ( n ) O(n) O(n)


二、 双指针算法的应用

1.拆分字符串中的单词

c++11 之后的版本不支持gets,因此使用scanf配合%[^ ]的方法来读取有空格的字符串输入。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
using namespace std;
int main()
{
	char str[1000];
	scanf("%[^
]", str); // 其中 %[^
] 表示读取到换行符之前的所有字符。
	int n = strlen(str);
	for (int i = 0; i < n; ++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 n n

第二行包含 n n n 个整数(均在 0 ∼ 1 0 5 0∼10^5 0105 范围内),表示整数序列。

输出格式:
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围:
1 ≤ n ≤ 105 1 ≤ n ≤ 105 1n105

输入样例:

5
1 2 2 3 5

输出样例:

3

朴素算法

for (int i = 1; i <= n; i++)
   for (int j = i; j <= n; j++)
        check(i, j); //看看i-j之间是不是存在某些数值重复

时间复杂度: O ( n 2 ) O(n^2) O(n2)

双指针算法

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

时间复杂度: O ( n ) O(n) O(n)

另类双指针算法

	// i 为快指针,j 为慢指针
	for (int i = 0, j = 0; i < n; ++i)
	{
		while (j <= i && check(j, i)) j++; // check(j, i)之间是不是存在某些数值重复
		res = max(res, j - i + 1);
	}

时间复杂度: O ( n ) O(n) O(n)
这种算法难点在于如何实现检查 [ j , i ] [j, i] [j,i] 之间的有无重复的元素(即 c h e c k ( j , i ) check(j, i) check(j,i))。

创建一个 s [ N ] s[N] s[N] 数组作为桶用来计入 [ j , i ] [j, i] [j,i] 之间出现的每个元素。

  • 维持一个窗口 [ j , i ] [j, i] [j,i],这个窗口里面保证是没有重复元素的,窗口大小从0开始。左侧有一个慢指针j,右侧有一个快指针 i i i

  • 当窗口中没有重复元素时,快指针向右,多吃进来一个。

  • 通过桶来判断是不是有重复出现,如果没有,则窗口最大长度 + + ++ ++

  • 如果有重复元素出现,则慢指针不断向右,直到找出并剔除重复元素,此时窗口变小。

  • 在窗口快慢指针的作用下,走完整个数组 i = = n i == n i==n,结束循环。

代码实现:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], s[N];// a-原数组 s-记个数的桶
int main()
{
	int n, res = 0;
	cin >> n;
	for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

	for (int i = 0, j = 0; i < n; ++i)
	{
		s[a[i]]++;
		while (s[a[i]] > 1) s[a[j++]]--;
		// 当s[a[i]] > 1 就是有了重复,则需要从窗口左侧尝试去掉一个
        // s[a[j++]]-- 不断刷新滑动容器长度,将直至到重复元素的部分剔除
		res = max(res, j - i - 1);
	}
	printf("%d", res);
	return 0;
}

3.数组元素的目标和

题目

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

输入格式:
第一行包含三个整数 n , m , x ,分别表示 A 的长度, B 的长度以及目标值 x 。 第一行包含三个整数n, m,x,分别表示A的长度,B的长度以及目标值x。 第一行包含三个整数n,m,x,分别表示A的长度,B的长度以及目标值x
第二行包含 n 个整数,表示数组 A 。 第二行包含n个整数,表示数组A。 第二行包含n个整数,表示数组A
第三行包含 m 个整数,表示数组 B 。 第三行包含m个整数,表示数组B。 第三行包含m个整数,表示数组B

输出格式:
共一行,包含两个整数 i 和 j 共一行,包含两个整数 i 和 j 共一行,包含两个整数ij

数据范围:
数组长度不超过 1 0 5 。同一数组内元素各不相同。 1 ≤ 数组元素 ≤ 1 0 9 数组长度不超过 10^5。同一数组内元素各不相同。1 ≤ 数组元素 ≤ 10^9 数组长度不超过105。同一数组内元素各不相同。1数组元素109

输入样例:

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

输出样例:

1 1

代码实现

一个从左侧出发,另一个从右侧出发。双指针,两边出发。双指针有序升序数组对向而行,和大了就 j−−,和小了就 i++。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
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 && j >= 0; ++i)
	{
		while (A[i] + B[j] > x && j > 0) j--;
		if (A[i] + B[j] == x) cout << i << ' ' << j;
	}
}

4.判断子序列

题目

给定一个长度为 n n n 的整数序列 a 1 , a 2 , . . . , a n a_1, a_2, . . . , a_n a1,a2,...,an 以及一个长度为 m m m 的整数序列 b 1 , b 2 , . . . , b m b_1, b_2,..., b_m b1,b2,...,bm

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

子序列指序列的一部分项按原有次序排列而得的序列,例如序列 a 1 , a 3 , a 5 a_1, a_3,a_5 a1,a3,a5 是序列 a 1 , a 2 , a 3 , a 4 , a 5 a_1, a_2, a_3, a_4, a_5 a1,a2,a3,a4,a5 的一个子序列。

输入格式:
第一行包含两个整数 n , m n, m n,m
第二行包含 n n n 个整数,表示 a 1 , a 2 , . . . , a n a_1, a_2,... , a_n a1,a2,...,an
第三行包含 m m m 个整数,表示 b 1 , b 2 , . . . , b m b_1, b_2,..., b_m b1,b2,...,bm

输出格式:
如果 a a a 序列是 b b b 序列的子序列,输出一行Yes。否则,输出No

数据范围:
1 ≤ n ≤ m ≤ 1 0 5 1 ≤ n ≤ m ≤ 10^5 1nm105
− 1 0 9 ≤ a i ≤ 1 0 9 -10^9 ≤ a_i ≤ 10^9 109ai109
− 1 0 9 ≤ b i ≤ 1 0 9 -10^9 ≤ b_i ≤ 10^9 109bi109

输入样例:

3 5
1 3 5
1 2 3 4 5

输出样例:

Yes

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N];
int main()
{
	int n, m;
	cin >> n >> m;

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

	int j = 0;
	for (int i = 0; i < m; ++i) if (b[i] == a[j]) ++j;
	if (j == n) printf("Yes");
	else printf("No");
	return 0;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。