4
双指针！
前言：
> 这是Stars_Seeker推出的学术计划系列的第二期，希望这个系列能够帮助到刚学习 C++ 或者复习 C++ 却不知道复习哪些的同学们，同时这个系列没有过多的言语和绝美的佳句作者语文不好（，只有透彻又不完全透彻的知识awa。
> 写的这么差的帖子肯定是AI（
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
双指针是什么
双指针可以看做对于枚举的一种优化。
对于两个指针如果分别从 1 到 n 枚举，那么两重循环嵌套，复杂度是 O(n^2),
但在一些具有单调性的题目中，可以使 i 指针和 j 指针都只需要从 1 到 n 遍历一次，复杂度分别为 O(n) , 总复杂度也是 O(n) 。
例题 1: P1147 连续自然数和
思路：构建前缀和数组，由于数字都大于 0，那么前缀和数组存在单调性，可以考虑双指针 i 指针移动时候，为了使得区间和仍然接近 n，j 指针只会向右移动，因此 i 指针和 j 指针都只需要从 1 到 n 遍历一次， 复杂度分别为 O(n) , 总复杂度也是 O(n) 。
代码实现
例题 2: P1102 A-B 数对
思路： 先排序使得数组存在单调性， 然后 i 指针从 1 到 n 扫一遍，复杂度为 O(n) , 每次找到符合条件的最大的 j ，将对应的数量加入答案，为了了解当前的 j 是同类数字里出现的第几个数字，可以另外开一个 cnt 数组来记录。为了保持 j 指针尽量大并且满足 a[i] - a[j] >= c ，当 i 指针向右移动时候, j 指针只会不变或者向右移动，那么 j 指针的总移动次数也是 O(n) 。
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
是的没错，你没有听错，第二期结束了！
比第一期稍微长了一点，因为加了2道例题。以后字数不够的时候凑字数就这么写 ）））
本篇文章中“代码的注释”部分内容是作者它询问了它的教练，所以会看起来很权威。
如果文章中出现质量问题或者还有其他思路,欢迎在评论区讨论
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
<-上一篇学术计划
有帮助，赞一个