双指针思想

  简单来讲，双指针思想是指在遍历对象的过程中，使用两个指针----相同方向（快慢指针）、不同方向（对撞指针），进行扫描，寻找满足题目要求的条件，从而降低时间复杂度的算法。

  双指针思想是很多算法的基础，如归并排序、滑动窗口、字符匹配等。

对撞指针通常适用于：

• 有序数组、有序链表，从中寻找满足条件的组合

• 可能是一对数、三个数或子数组
  

快慢指针通常用于：

• 问题需要处理环上的问题，比如环形链表和环形数组

• 当你需要知道链表的长度或是某个特别位置的信息的时候

例题：

对撞指针：

题解：

快慢指针：

  题解：

  数组已经有序，并且要求使用原地算法，只要输出新数组的长度即可，多余的部分不做考虑。因此我们定义left，right左右两个快慢指针：

• 快指针先遍历，当遇到不重复的元素时，慢指针向前移动一步。

• 将快指针当前的元素复制到慢指针位置，继续遍历。

• 最后返回 left+1。

参考：

https://zhuanlan.zhihu.com/p/104983442