Skip to main content

Array Two Pointers 双指针

双指针方向​

双指针将一个 Array 分成两到三部分，根据指针移动的方向，

  • i, j 同向情况下，分为 已处理需要保留数据，已处理不需要的数据 和 未处理数据。
  • i, j 相向情况下，分为 已处理数据 和 未处理数据。

双指针同向​

[0, i) 数据代表处理好的数据, [i, j)中的数据是已经处理过但不需要的数据, [j, array.length)区间的数据为接下来待处理的数据。注意区间的开闭，这将帮助我们理解题意。此方法处理数据的相对位置会保持一致。

通用步骤​

  1. 定义两个指针 i 和 j, 通常两个都会等于零，也可以是数组的末尾开始 array.length-1;
  2. while j < array.length: 如果 j 的位置没有到达数组的末尾，则运行下一步逻辑
    • 如果我们判断 j 位置的数据是我们需要的时候，运行 array[i]=array[j], 此处 i 表示我们保留的所有数据的情况下的下一个值的位置，我们把 j 位置的值保留到 i 中，然后移动 i 到下一个位置。
    • 除此之外，我们不会做任何动作，只有 j 会继续移动，i 因为没有新的数据并不会移动位置。

双指针反向​

[0, i) 和 (j, array.length), [i, j]中的数据待处理。此方法处理数据的相对位置不会保持一致。

通用步骤​

  1. 定义两个指针 i=0 和 j=array.length-1;
  2. while i <= j
    • 根据 array[i] 和 array[j] 的值来决定做什么
    • 移动至少一个指针前进，避免死循环

更多例题​

  1. Reverse String (344) -> Done
  2. Remove Duplicates From Sorted Array (26) -> Done
  3. Container With Most Water (11) -> Done
  4. Trapping Rain Water (42) -> Done
    • 理解 Math.min(maxLeft, maxRight) - height[n]
    • 双位置指针情况，需要针对 maxLeft 与 maxRight 的地势走向有不同的计算
    • 最终不要忽略双位置指针相等时，依然要进行一次计算，以免漏算一个格子中的水
    • 解法讲解: https://www.youtube.com/watch?v=C8UjlJZsHBw
  5. Move Zeros (283) -> Done
  6. Remove Duplicates From Sorted Array II (80) -> Done
  7. Remove All Adjacent Duplicates In String (1047) -> Done

来源​