Two Pointers Technique

介绍

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

用法

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

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

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

while (front < tail)
  {
    ....
  }

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

使用范围

一般双指针在有序数组中使用的特别多。(部分情况下，未排序数组也有应用)一般用来解决下列问题

• 两数求和
  一般这种问题都是问，寻找两个数的和为一个特定值，这时候，如果数组有序，我们采用两个指针，分别从
  前和后往中间遍历,front移动和增大，tail移动和减小，通过特定的判断，可以求出特定的和
  时间复杂度为O(n)，如果要使用双重循环则时间复杂度为O($n^{2}$)

• in place 交换
  数组的in place原地交换一般都得用双指针，不然数组中添加或这删除一个元素，需要移动大量的元素。这时候一般是一个指针遍历，一个指针用来找可以交换的元素。