介绍
双指针是一种思想,一种技巧或一种方法,并不是什么特别具体的算法,在二分查找等算法中经常用到这个技巧。具体就是用两个变量动态存储两个或多个结点,来方便我们进行一些操作。通常用在线性的数据结构中,比如链表和数组,有时候也会用在图算法中。
在我们遇到像数组,链表这类数据结构的算法题目的时候,应该要想得到双指针的套路来解决问题。特别是链表类的题目,经常需要用到两个或多个指针配合来记忆链表上的节点,完成某些操作。链表这种数据结构也是树形结构和图的原型,所以有时候在关于图和树形结构的算法题目中也会用到双指针。
当你遇到此类数据结构,尝试使用双指针来解题的时候,可以从以下几个双指针类题目的套路入手进行思考
用法
一般来讲,当遇到需要对一个数组进行重复遍历时,可以想到使用双指针法。
判断指针移动的条件是双指针的核心
类型
快慢指针
类似于龟兔赛跑,两个链表上的指针从同一节点出发,其中一个指针前进速度是另一个指针的两倍。利用快慢指针可以用来解决某些算法问题,比如
- 计算链表的中点:快慢指针从头节点出发,每轮迭代中,快指针向前移动两个节点,慢指针向前移动一个节点,最终当快指针到达终点的时候,慢指针刚好在中间的节点。
- 判断链表是否有环:如果链表中存在环,则在链表上不断前进的指针会一直在环里绕圈子,且不能知道链表是否有环。使用快慢指针,当链表中存在环时,两个指针最终会在环中相遇。
- 判断链表中环的起点:当我们判断出链表中存在环,并且知道了两个指针相遇的节点,我们可以让其中任一个指针指向头节点,然后让它俩以相同速度前进,再次相遇时所在的节点位置就是环开始的位置。
- 求链表中环的长度:只要相遇后一个不动,另一个前进直到相遇算一下走了多少步就好了
- 求链表倒数第k个元素:先让其中一个指针向前走k步,接着两个指针以同样的速度一起向前进,直到前面的指针走到尽头了,则后面的指针即为倒数第k个元素。(严格来说应该叫先后指针而非快慢指针)
碰撞指针
一般都是排好序的数组或链表,否则无序的话这两个指针的位置也没有什么意义。特别注意两个指针的循环条件在循环体中的变化,小心右指针跑到左指针左边去了。常用来解决的问题有
1. 二分查找问题
2. n数之和问题:比如两数之和问题,先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推。
滑动窗口法
两个指针,一前一后组成滑动窗口,并计算滑动窗口中的元素的问题。
这类问题一般包括
1、字符串匹配问题
2、子数组问题
标签:两个,思想,链表,算法,数组,节点,指针 From: https://www.cnblogs.com/yccy/p/17539570.html