双指针算法

基本思想

双指针算法的类型

双指针指向两个序列-类似于归并排序

归并排序指针图示

双指针指向同一个序列-类似于快排

快速排序指针图示

核心思想

双指针算法的核心思想

算法模板

双指针算法的通用模板

大致的通用模板

示例运用

示例题目一

输出用空格隔开的每个单词，输出的每个单词占单独的一行。

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

#include <iostream>
#include <string.h>

using namespace std;

int main()
{
	char str[1000];
	gets(str);

	int n = strlen(str);

	for (int i = 0; i < n; i++)
	{
		int j = i;
		while (j < n && str[j] != ' ') j++; // i指向单词的开头，j指向单词的结尾
		// 这道问题的具体逻辑
		for(int k = i; k < j; k++) printf("%c",str[k]);
		printf("\n");
		i = j;
	}
	system("pause");
	return 0;
}

示例题二

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

输入格式

第一行包含整数 n。

第二行包含 n 个整数（均在 0∼10e5范围内），表示整数序列。

输出格式

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

数据范围

1≤n≤10e5

输入样例：
1
2

5
1 2 2 3 5
输出样例：
1

3

算法的思考过程-从朴素到优美 算法的思考过程

 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
29
30

#include <iostream>
#include <string.h>

using namespace std;

const int N = 100010;

int n;
int a[N], 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 << endl;
	system("pause");
	return 0;
}

算法没理解可以用手动模拟一下！