文章目录
前言
一、双指针算法概述
二、双指针算法模板及例题
1.模板
2.AcWing799. 最长连续不重复子序列
AC代码
代码分析
3.AcWing 800. 数组元素的目标和
AC代码
代码分析
4.AcWing2816. 判断子序列
AC代码
代码分析
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：双指针算法，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上
一、双指针算法概述
这里的指针不是我们知道的 * ，这里的双指针是例如用 i 和 j 去维护一段区间，大致形式如：
for (int i = 0; i < n; i ++ ) for (int j = 0; j < i; j ++ ) { ...... }
二、双指针算法模板及例题
1.模板
本算法模板来自：AcWing算法基础课
for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; //check函数指 i，j之间除了j < i的其他关系 // 具体问题的逻辑 }
2.AcWing799. 最长连续不重复子序列
本博客给出题目截图：
AC代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 100010; int a[N], s[N]; int main() { int n, ans = 0; scanf("%d", &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]] --; j ++; } ans = max (ans, i - j + 1); } printf("%d", ans); return 0; }
代码分析
本题利用双指针算法，因为题目保证 a[i] 中的每一个数都是属于[0, 1e5] 的，所以可以用s[a[i]]去存储 a[i] 出现了多少次，每出现一次就把 s[a[i]] ++; 所以如果当 s[a[i]] > 1 的时候就证明出现了重复的数字，本题双指针算法维护的是从 j 开始到 i 结束的这么一段子区间，只要不满足 s[a[i]] > 1 这一条件，j 就不动，i 往后移动一个单位，直到出现了 s[a[i]] > 1，证明维护的这一子区间内出现了重复的元素，我们就把 j 往后移动一位，每次 i 更新的时候都计算一下当前子区间的长度更新 ans.
for (int i = 0, j = 0; i < n; i ++ ) //因为j始终是小于i的，所以当i走到终点即可 { s[a[i]] ++; while (s[a[i]] > 1) { s[a[j]] --; j ++; } ans = max (ans, i - j + 1); }
3.AcWing 800. 数组元素的目标和
本题链接：AcWing 800. 数组元素的目标和
本博客给出本题截图：
AC代码
#include <cstdio> using namespace std; const int N = 100010; int a[N], b[N]; int main() { int n, m, x; 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 (a[i] + b[j] > x) j --; //这里的while中不需要加 j >= 0，因为保证一定有解 if (a[i] + b[j] == x) { printf("%d %d", i, j); break; //找到目标值就退出，因为保证有唯一解 } } return 0; }
代码分析
如下代码会TLE：这个代码就是纯暴力代码了，时间复杂度是O(n²)，那么对比我们这个代码和AC的代码，AC的代码优化在哪里了呢？
//错误代码： for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (a[i] + b[j] == x) { printf("%d %d", i, j); exit(0); //exit(0); 需要添加头文件 #incldue <cstdlib> }
这个错误代码 i 和 j 都是从 0 开始的，而AC的代码中 i 是从0开始的，j 是从 m - 1开始的，即数组a是正序遍历，数组b是逆序遍历，这么遍历的优点在于，因为数组a和数组b都是满足严格上升的，如果满足 i + j > x 的条件，那么 i 是不需要再往后移动的，只需要 j 往前移动就好了，正所谓双向的奔赴要好于单方向的追求，i 和 j 同时向一个值靠近要优于 i 和 j 一直试错的靠近.
4.AcWing2816. 判断子序列
本题链接：AcWing2816. 判断子序列
本博客给出本题截图：
AC代码
#include <cstdio> using namespace std; const int N = 100010; int a[N], b[N]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]); int i = 0, j = 0; for (;i < n && j < m; j ++ ) if (a[i] == b[j]) i ++; if (i == n) puts("Yes"); else puts("No"); return 0; }
代码分析
判断数组a是否是数组b的子序列：
如图，我们依次对比a数组和b数组的每一个元素，如果不匹配的话，就让数组b向后移动一个单位，如果匹配的话就让数组b和数组a都往后移动一个单位，如果最后a数组的每一个元素在数组b中都有对应元素，则输出Yes，否则输出No
int i = 0, j = 0; for (;i < n && j < m; j ++ ) if (a[i] == b[j]) i ++;
三、时间复杂度
关于双指针算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
