双指针

介绍

开始，这章的题目是叫“数组”，但是，目前更名为双指针，这是因为我发现凡是数组的题目，大部分都是利用双指针去解决问题。

双指针，顾名思义，就是利用两个指针去遍历数组，一般来说，遍历数组采用的是单指针（index)去遍历，两个指针一般是在有序数组中使用，一个放首，一个放尾，同时向中间遍历，直到两个指针相交，完成遍历，时间复杂度也是O(n)。

用法

一般会有两个指针front,tail。分别指向开始和结束位置。

  1.   front = 0;
  2.   tail = A.length()-1

一般循环结束条件采用的是判断两指针是否相遇

  1.   while(fron < tail)
  2.   {
  3.   ……
  4.   }

对于in place交换的问题，循环结束条件一般就是其中一个指针遍历完成。

使用范围

一般双指针在有序数组中使用的特别多。（部分情况下，未排序数组也有应用）
一般用来解决下列问题（陆续补充中）：

1. 两数求和

一般这种问题是问，寻找两个数的和为一个特定的值（比如后面的N SUM问题），这时候，如果数组有序，我们采用两个指针，分别从前和后往中间遍历，front移动和增大，tail移动和减小，通过特定的判断，可以求出特定的和。

时间复杂度为O(n),如果用双重循环则要O(n^2)。

2. in place交换

数组的in place(就地)交换一般得用双指针，不然数组中添加或删除一个元素，需要移动大量元素。

这时候，一般是一个指针遍历，一个指针去找可以用来交换的元素。