概述

讨论一下数组中的双指针相关算法

移除元素

描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

实现

冒泡版

最初想到的这个有点像冒泡排序，即把需要删除的元素全部往数组后面排，再单独找出新数组长度。该方式简单粗暴，比较容易想到，但是时间复杂度为 O(n^2)，实现为下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
removeElement1(nums, val) {
      let flagValue = null;
      let num = 0;
      for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length - 1 - i; j++) {
          if (nums[j] === val) {
            flagValue = nums[j];
            nums[j] = nums[j + 1];
            nums[j + 1] = flagValue;
          }
        }
      }
      for (let k = 0; k < nums.length; k++) {
        if (nums[k] !== val) {
          num++;
        }
      }
      return num;
    },

优化版

由于上面代码循环太多次，涉及到 3 个 for 循环，实际运行效率非常低，优化为下：

1
2
3
4
5
6
7
8
9
10
11
12
13
removeElement2(nums, val) {
      let size = nums.length;
      for (let i = 0; i < size; i++) {
        if (nums[i] === val) {
          for (let k = i; k < size - 1; k++) {
            nums[k] = nums[k + 1];
          }
          i--;
          size--;
        }
      }
      return size;
    },

双指针版

上面的版本时间复杂度依然没有满足要求，最后采用双指针法，解决该问题：

1
2
3
4
5
6
7
8
9
10
removeElement3(nums, val) {
      let flag = 0;
      for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== val) {
          nums[flag] = nums[i];
          flag++;
        }
      }
      return flag;
    }

双指针法代码简洁优美，时间复杂度为 O(n)，比最初自己写的版本不知高到哪里去了…

我太菜了。

算法地址

移除元素

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

算法地址

该题解法也是双指针方式，代码如下：

1
2
3
4
5
6
7
8
9
10
removeDuplicates(nums) {
      let flag = 0;
      for (let i = 1; i <= nums.length; i++) {
        if (nums[i - 1] !== nums[i]) {
          nums[flag] = nums[i - 1];
          flag++;
        }
      }
      return flag;
    }

双指针方式：设置一个正常的遍历指针，一个慢指针。当满足条件时，把原数组中的元素用慢指针覆盖。这样得出的数组即为所求数组，而慢指针的值，即为新数组的长度，超出该长度的数组空间可以视为垃圾数据。

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

题目链接

可以先收集非零元素，然后记住非零元素个数（index)，最后把数组剩余空间全部置 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
moveZeroes(nums) {
      // [0,1,0,3,12]
      let flag = 0;
      let size = nums.length;
      for (let i = 0; i < size; i++) {
        if (nums[i] !== 0) {
          nums[flag] = nums[i];
          flag++;
        }
      }
      for (let k = flag; k < size; k++) {
        nums[k] = 0;
      }
      return flag;
    },

上面的解法还是不大简洁，看看大佬写的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
moveZeroes(nums) {
      // [0,1,0,3,12]
      let flag = 0;
      let size = nums.length;
      for (let i = 0; i < size; i++) {
        if (nums[i] !== 0) {
          nums[flag++] = nums[i];
        }
      }
      while (flag < size) {
        nums[flag++] = 0;
      }
      return nums;
    },

果然大佬还是太强了…

比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

题目链接

基本思路：把字符串转换为数组，然后使用双指针方法，设置一个慢指针，遍历数组；当检测到#号时，慢指针-1，并且使得数组中慢指针对应的空间存储对应值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
backspaceCompare(s, t) {
      const formatString = (string) => {
        let list = string.split("");
        // [a,b,#,c]
        let flag = 0;
        let size = list.length;
        for (let i = 0; i < size; i++) {
          if (list[i] !== "#") {
            list[flag++] = list[i];
          } else {
            if (flag > 0) {
              flag--;
            }
          }
        }
        let newStr = "";
        for (let i = 0; i < flag; i++) {
          newStr = newStr + list[i];
        }
        return newStr;
      };
      let newS = formatString(s);
      let newT = formatString(t);
      return newS === newT;
    }

该算法时间复杂度为 O(n),空间复杂度为 O(n)

该算法还有实现方式为 O(1)的实现思路

准备两个指针 ii, jj 分别指向 SS，TT 的末位字符，再准备两个变量 skipSskipS，skipTskipT 来分别存放 SS，TT 字符串中的 # 数量。
从后往前遍历 SS，所遇情况有三，如下所示：

2.1 若当前字符是 #，则 skipSskipS 自增 11；

2.2 若当前字符不是 #，且 skipSskipS 不为 00，则 skipSskipS 自减 11；

2.3 若当前字符不是 #，且 skipSskipS 为 00，则代表当前字符不会被消除，我们可以用来和 TT 中的当前字符作比较。

若对比过程出现 SS, TT 当前字符不匹配，则遍历结束，返回 falsefalse，若 SS，TT 都遍历结束，且都能一一匹配，则返回 truetrue。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var backspaceCompare = function (S, T) {
  let i = S.length - 1,
    j = T.length - 1,
    skipS = 0,
    skipT = 0;
  // 大循环
  while (i >= 0 || j >= 0) {
    // S 循环
    while (i >= 0) {
      if (S[i] === "#") {
        skipS++;
        i--;
      } else if (skipS > 0) {
        skipS--;
        i--;
      } else break;
    }
    // T 循环
    while (j >= 0) {
      if (T[j] === "#") {
        skipT++;
        j--;
      } else if (skipT > 0) {
        skipT--;
        j--;
      } else break;
    }
    if (S[i] !== T[j]) return false;
    i--;
    j--;
  }
  return true;
};