Array题型 之 双指针(Two Pointers)

双指针分为同向双指针和反向双指针,这里我们一一来进行说明:

Two Pointers 同向

图解:

• 其中的[0 , i)的数据代表的是已经处理好且需要保留的数据,[i , j)中的数据是处理过但是不需要的数据, [j , array.length)是待处理的数据
  • 这里的三个区间的开和闭都是要根据题目的要求来定义, 但是一定要注意:这三个区间的定义一定要是一致的,也就是我们的三开区间要么都是左开右闭,要么都是左闭右开
    • 但是一般情况之下都是左闭右开 —>也就是i指向的前一个数据为最后一个处理过并且是不保留的数据,j指向的位置是接下来的第一个要执行的数据的位置

注意: 使用Two Pointers同向处理过的数组,其中处理好的数据的相对位置是和原来保持一致的 —> 这一点很重要

通用步骤:(一般情况之下)

1. i 和 j 都是从0开始()
2. while(j < array.length)
   • 如果我们需要array[j]的值,我们就将array[j]的值赋值给array[i],这个时候一旦array[i]被赋值之后i 就要后移, 这个时候一旦 array[j]赋值之后 j 就要后移
   • 如果不需要array[j]的值,这个时候我们的i的位置不变 , j后移

Two Pointers 反向

图解:

• 其中[0 , i) 和 (j , array.length]内的数据均为处理好的数据,[i , j]中的数据都是待处理的数据

注意: 用Two Pointers反向处理过的数组不会保留原来元素的相对位置

通用步骤(一般情况之下)

1. i 初始为0, j初始为array.length - 1
2. while(i <= j)
   • 这里我们需要对i和j位置做一些基本操作(就比如: 让i 和 j位置的元素交换位置,或者让i 或者 j位置上元素值小的位置向中间移动等等)
   • 但是一定要注意: 我们每一次至少要移动一个指针,否则就可能出现死循环的问题(就比如我们的快速排序 --> 我们的快速排序中就是使用了双指针的思想)
     • 如果一个指针都不移动, 那么就有可能会出现死循环的问题