算法技巧——双指针算法

前置知识

C 和 C++ 的数组、指针。

什么是双指针

严格的来说，双指针只能说是是算法中的一种技巧。

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

双指针问题套路

通俗的说，就是在数组遍历中，我们使用两个指针进行操作。所以双指针问题基本有以下几个细节：

1、双指针的初始位置。根据双指针的分类，有两种可能。具体看下面的介绍。

2、双指针的移动方法。根据双指针的分类，有两种可能。具体看下面的介绍。

3、遍历的结束条件。根据双指针的分类，有两种可能。具体看下面的介绍。

对撞指针

对撞指针是指在数组中，将指向最左侧的索引定义为左指针（left），最右侧的定义为右指针（right），然后从两头向中间进行数组遍历。快速排序就是典型的双指针问题。

我们假设数组名字为 nums，数组长度为 n，数组首元素对应的位置为 0。

代码细节

指针初始位置

左指针（left)一般指向数组的第一个元素。即 left = 0。

右指针（right)一般指向数组的第一个元素。即 right = n-1。

指针移动方法

左指针(left）向右边