双指针

介绍

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

双指针,顾名思义,就是利用两个指针去遍历数组,一般来说,遍历数组采用的是单指针(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(就地)交换一般得用双指针,不然数组中添加或删除一个元素,需要移动大量元素。

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