一.基础

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

• 具体思路一是：初始化两个指针，一个指向数组的第一个元素，另外一个指向数组的最后一个元素，在两个指针相遇之前，指针1只能向前移动，指针2 只能向后移动。比较当前两个指针所指元素和与给定数字的大小，如果和较大，指针2向后移动，如果和较小，指针1向前移动。最终的结果是找到两个满足条件的数或者不存在这样的两个数字。

• 具体思路二是：快慢指针

二. 套路

1. 快慢指针（相同方向指针进行扫描）

• 计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。
• 判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。
• 判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
• 求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了
• 求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。（严格来说应该叫先后指针而非快慢指针）

2. 碰撞指针（相反方向指针进行扫描）

• 二分查找问题

• 归并排序

• n数之和问题：比如两数之和问题，先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推

3. 滑动窗口法

• 字符串匹配问题
• 子数组问题

三. 做题总结

• 双指针算法的 “套路”： 两个指针各有一个初始位置 两个指针各有一个移动方向 移动停止的条件：其中一个指针到底了，两个指针相遇了，找到答案了 …