常用的双指针技巧

什么是双指针？其实很好理解，双指针是一种思想，一种技巧或一种方法，并不是什么特别具体的算法，在二分查找等算法中经常用到这个技巧。具体就是用两个变量动态存储两个或多个结点，来方便我们进行一些操作。通常用在线性的数据结构中，比如链表和数组，有时候也会用在图算法中。

在我们遇到像数组，链表这类数据结构的算法题目的时候，应该要想得到双指针的套路来解决问题。特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。链表这种数据结构也是树形结构和图的原型，所以有时候在关于图和树形结构的算法题目中也会用到双指针。

一、概述

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。

双指针是指在遍历对象时，使用两个或多个指针进行遍历及相应的操作。大多用于数组操作，这利用了数组连序性的特点。双指针常用来降低算法的时间复杂度，因为使用两个指针可以避免多层循环。

双指针的三个关键点：

（1）指针的起始位置的选取

（2）指针的移动方向

（3）指针的移动速度

这三个关键点是双指针算法的核心也是难点，

二、算法题型

在时间或空间条件有限的情况下使用单向遍历需要消耗大量的时间或者根本无法解决问题，这时候就需要我们使用双指针，通过指针的碰撞判断是否达到条件，从而解决问题。

（一）左右指针

左右指针通常在数组有序的情况下，从最小和最大端同时对数组进行处理，对满足特定条件的数组元素进行成对处理，快慢指针逐渐靠拢直至发生碰撞，则遍历完所有数组。

举个例子：

一个孤岛上有7个人重量54kg，55kg，56kg，57kg，58kg，59kg，70kg。她们需要逃生到安全的地方。现在有足够的救生艇，但是每个救生艇只能坐两个人，而且每个救生艇最大能承受113kg的重量，那她们最少需要多少救生艇才能全部逃生。

现在我们来分析，如果最重的人可以与最轻的人共用一艘船，那么就这样安排。否则，最重的人无法与任何人配对，那么他们将自己独自乘一艘船。这么做的原因是，如果最轻的人可以与任何人配对，那么他们也可以与最重的人配对。

那我们首先让她们按照体重排好队

那我们首先看最瘦的和最胖的，连个加起来有124斤，是坐不了一条船的

那我们只能让最胖的自己坐一条船，然后看第二胖的能不能和最瘦的一起坐船走，这时候用了一条船。

可以发现最瘦的果然和第二胖的人体重一共为113kg，她们是可以一起坐船走的，这时候一共占用了两条船，接下来继续看第二瘦和第三胖的人。

最后组队情况为：

54kg - 59kg，55kg - 58kg，56kg - 57kg，70kg

从上我们可以看到双指针即是在有序数组的情况下，我们通过两个指针在遍历的过程中进行标记，对满足条件的进行处理，直至遍历完整个数组。

（二）快慢指针

快慢指针中的快慢即两个指针移动的快慢不同，通过两个指针移动速度的不同，判断数组或链表的长度、是否有环、特定位置的数值等。

举个例子：

假如有一条跑道，假如有环，会沿着环一直跑，乌龟每次走一步，兔子每次走两步，那么如果有环，那么他们必定会相遇，过程如下：

一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。