一、常见类型
(1) 对于一个序列，用两个指针维护一段区间（如：快排）
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作（如：归并排序）
二、模板
1 for (int i = 0, j = 0; i < n; i ++ )
2 {
3 while (j < i && check(i, j)) j ++ ;
4
5 // 具体问题的逻辑
6 }
三、核心思想及时间复杂度
核心思想：优化
暴力算法： O（n²）
1 for (int i = 0; i < n; i++) 2 for(int j = 0; j < n; j++)
双指针算法：O（n）
四、例题
1、输入一个字符串，每个单词用一个空格隔开，输出其中的单词，每个单词占一行。
如： 输入 abc def gh
输出 abc
def
gh
1 1 #include <iostream>
2 2 #include <string.h>
3 3 using namespace std;
4 4
5 5 int main()
6 6 {
7 7 char str[1000];
8 8 gets(str);
9 9 int n = strlen(str);
10 10 for(int i = 0; i < n; i++)
11 11 {
12 12 int j = i;
13 13 for(j<n && str[j] != ' ') j++;
14 14
15 15 //这道题的具体逻辑
16 16 while(int k = i; k < j; k++) cout << str[k];
17 17 cout << endl;
18 18 i = j;
19 19 }
20 20 return 0;
21 21 }
2、最长连续不重复子序列
暴力算法：O（n²）
1 for(int i = 0; i < n; i++)
2 for(int j = 0; j <= i; j++)
3 if(check(j,i))
4 {
5 res = max(res,i-j+1);
6 }
双指针算法：O（n）
1 for(int i = 0， j = 0; i < n; i++)
2 {
3 while(j <= i && check(j,i)) j++;
4 res = max(res,i-j+1);
5 }
优化：j无需从0开始遍历，只需从i开始即可
1 #include <iostream>
2 using namespace std;
3 const int N = 1e5 + 10;
4
5 int a[N], s[N];
6 int n;
7
8 int main()
9 {
10 cin >> n;
11 for(int i = 0; i < n; i++) scanf("%d", &a[i]);
12 int ans = 0;
13 for(int i = 0, j = 0; i < n; i++)
14 {
15 s[a[i]]++;
16 while(j<i && s[a[i]]>1)
17 {
18 s[a[j]]--;
19 j++;
20 }
21 ans = max(ans,i-j+1);
22 }
23 cout << ans;
24 return 0;
25 }
五、思路
先写出暴力解法O（n²），然后观察i和j的关系（是否具有单调性），如果有，则利用单调性，利用双指针优化到O（n）
注意：时间复杂度看的不是循环嵌套次数，而是看重复遍历了几次。
标签：10,int,++,算法,include,指针 From： https://www.cnblogs.com/FISHCat-cjp/p/17234640.html