您现在的位置是:首页 >其他 >双指针算法网站首页其他
双指针算法
一、双指针算法的概念
【核心思想】
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 0∼105 范围内),表示整数序列。
输出格式:
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围:
1
≤
n
≤
105
1 ≤ n ≤ 105
1≤n≤105
输入样例:
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 。
给定两个升序排序的有序数组A和B,以及一个目标值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
共一行,包含两个整数i和j。
数据范围:
数组长度不超过
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
1≤n≤m≤105
−
1
0
9
≤
a
i
≤
1
0
9
-10^9 ≤ a_i ≤ 10^9
−109≤ai≤109
−
1
0
9
≤
b
i
≤
1
0
9
-10^9 ≤ b_i ≤ 10^9
−109≤bi≤109
输入样例:
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;
}