Fl0w3r

carpe diem

Two Pointers

Posted on In
2.8k 5 mins.

引言

Array是最基础也是最常见的数据结构，以下我们会介绍array题目中最常用的双指针（two pointers）方法，可以用于解决一系列常见的array题目。本章会讲解双指针常见的套路，然后再结合题目帮助大家深入理解如何应用双指针。

双指针 Two Pointers

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

同向双指针

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

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

[1, 2, 0, 3, 0, 8] move zeros to the end –> [1, 2, 3, 8, 0, 0], not [8, 2, 3, 1, 0, 0] or others

同向双指针的解题步骤如下：

  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] 中的数据待处理。用此方法处理过的数组不会保留原来元素的相对位置。解题步骤如下：

  1. Initialize two pointers i = 0, j = array.length – 1
  2. 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

实践应用

接下来我们就来讲解两道经典题目，帮助大家深入理解如何使用双指针套路。

例题 344. Reverse String

这是一道很经典的字符串反转问题，如果可以使用上文的双指针套路，那么应该采取同向还是反向呢？根据观察调换字符串的规律，我们发现只要从外往里，不断调换头部和尾部的元素就能颠倒一个字符串，那很明显和我们提到的反向双指针相关。

以下为解题代码：

class Solution {
public:
    void reverseString(vector<char>& s) {
      	// initialize
        int i = 0, j = s.size() - 1;

        while(i < j) {
          // swap str[i] and str[j]
            swap(s[i], s[j]);
            i++;
            j--;
        }
    }
};

这里我比较偷懒用了 swap() 函数，也可以朴素一点设置一个变量两两交换：

class Solution {
public:
    void reverseString(vector<char>& s) {
      	// initialize
        int i = 0, j = s.size() - 1;

        while(i < j) {
          // swap str[i] and str[j]
          char buffer = str[i];
          str[i] = str[j];
          str[j] = buffer;

          i++;
          j--;
    }
}

例题 26. Remove Duplicates From Sorted Array

此题要求我们删除重复字符，要注意的是去重之后元素的相对位置不能改变，比如 [1, 2, 2, 3] 去重后是 [1, 2, 3]，而不能是 [1, 3, 2]。既然输入数组是排好序的，那么对于每段重复元素，他们必定是相连的，我们只需要记录头元素即可，然后依次记录下那些互不重合的元素，就能解决此题了。这种需要依次记录下所需要元素的问题，就能完全使用同向指针的套路来解决，以下是解题步骤和代码：

  1. Initialize two pointers i = 0, j = 0
  2. while j < array.length:
    • if array[j] != array[i – 1], meaning it’s not a duplicate of what we had so far, then we keep it by array[i++] = array[j++]. Remember by definition [0, i) is already processed, not including i, so the last processed element is i – 1.
    • otherwise, it’s a duplicate of array[i], skip it with j++
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // initialize
        int i = 0, j = 0;
        while (j < nums.size()) {
            // if not duplicate, keep it, otherwise skip it
            if (i == 0 || nums[j] != nums[i - 1])
                nums[i++] = nums[j++];
            else
                j++;
        }

        // i is now at the length of the new array, [0, i) is what we want
        return i;
    }
};

简单来说，[0 ~ i) 区间的元素是我们决定留下来的元素，i 指向的位置需要放入的是下一个不重复元素，j 指针是用来遍历整个数组的。在遍历过程中，如果 array[j] 和 array[i – 1] 不同，代表出现了一个新的不重复元素，那么就将新元素赋给 array[i]，否则向右移动 j 指针，直到 j 指针遍历完整个数组为止。

总结

可见双指针是用来解决很多常见数组题目的利器，其中包括同向和反向两个变种，大家需要根据题目的要求对三个区间的定义做相对应的调整。以下是和双指针相关的经典题目，大家可以通过实践来巩固此套路：

  1. Container With Most Water (11)
  2. Trapping Rain Water (42)
  3. Move Zeros (283)
  4. Remove Duplicates From Sorted Array II (80)
  5. Remove All Adjacent Duplicates In String (1047)
Related Posts