双指针
萌新求赞求收藏求关注qaq
如果有误,望指正!
翻自己$blog$时候突然发现双指针落下了。
今天窝补上。
前景
有一道十分困难的题目。
在一个单调数组上找到两个点,使得他们满足某种性质。
或者说两个点也可以改成一个区间。
有两种解法,一种是快慢指针,另一种是左右指针。
本文主要介绍第一种。
先说暴力解法。
for(1->n)
for(i+1->n)
if(check())
.....
很明显,这里是 $O(N^2)$ 的时间复杂度。
如果 $N$ 飙升到 $10^5$ 甚至 $10^6$ ,很明显这个复杂度是不能接受的。
优化
那么之前说到了单调性。
可以用这个搞点东西。
之前说过二分。(不挂link了,你们自己翻下吧qwq,在很前面的位置
二分就是在具有单调性质的数组里进行折半查找。
而这一次我们的出发点是:是不是有时间被浪费了。
我们看一下,比如说找一段数的和。
这时候,我们会发现,当 $i$ 运行到时候,后面的j要花大的时间去一次次找。
这事情是很浪费时间的。
那么,我们就人 $j$ 像 $i$ 的尾巴一样,跟在 $i$ 的后面。
专业一点的话说,我们不让 $j$ 指针回退。
这样的话,效率会提高很多。
具体一些,就是说,让 $i$ 正常的走,然后在里面进行while
循环,把 $j$ 尽可能往前跟。
那么,这就是$O(N)$的复杂度了。
这就是双指针算法。
人没有尾巴吧(
左右指针还没更新欸
two points
嗯