双指针 Two Pointers

Array是最基础也是最常见的数据结构，和Array同样频繁出现的String也可以看做是一个char array。通常我们需要通过index来访问array中的元素，所以要处理array的题目自然少不了使用index pointers

双指针 Two Pointers

双指针（Two Pointers）是一种通过使用两个index pointers操作数组的方法，使用双指针来迭代数组的话，一个array会被分为三个区域：[0, i), [i, j), [j, array.length)。使用双指针时，我们必须要清楚地定义好每一块区域的含义，才能进行后续的解题。双指针解法一般分两种：同向和反向。

同向双指针

在同向双指针套路中，两个指针朝相同方向移动，但是快慢不同。其三个区域会被分割为下图所示：

其中 [0, i) 的数据代表处理好的数据，[i, j) 中的数据是那些处理过但不需要的数据，[j, array.length) 区间的数据为接下来待处理的数据。这里的三个区间的开和闭需要根据题目要求定义，但是要保持一致。用此方法处理过的数组，处理好的数据的相对位置要保持一致的。同向双指针的解题步骤如下：

1. Initialize two pointers i and j, usually both equal to 0

2. while j < array.length:

   • if we need array[j], then we keep it by assigning array[i] = array[j], and move i forward, make it ready at the next position
   • otherwise skip it. We do not need to move i since its spot is not fulfilled

     反向双指针

     反向双指针中的两个指针反向而行，同样分为三个区间：
     
     其中 [0, i) 和 (j, array.length) 内的数据均为处理好的数据，[i, j] 中的数据待处理。用此方法处理过的数组不会保留原来元素的相对位置。解题步骤如下：

3. Initialize two pointers i = 0, j = array.length – 1

4. while i <= j:
   • Decide what you should do based on the value of array[i] and array[j]
   • Move at least one pointer forward in its direction

例题

334. 反转字符串

334. 反转字符串

26. 删除排序数组中的重复项

语雀内容

11. 盛最多水的容器

语雀内容