双指针

本页面将简要介绍双指针。

引入

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。

接下来我们来看双指针的几个具体使用方法。

维护区间信息

如果不和其他数据结构结合使用，双指针维护区间信息的最简单模式就是维护具有一定单调性，新增和删去一个元素都很方便处理的信息，就比如正数的和、正整数的积等等。

例题 1

过程

设两个指针分别为 \(l,r\), 另外设置一个变量 \(\mathit{tmp}\) 记录 \([l,r]\) 内所有数的乘积。最开始 \(l,r\) 都在最左面，先向右移动 \(r\)，直到第一次发现 \(\mathit{tmp}\geq k\), 这时就固定 \(r\)，右移 \(l\)，直到 \(\mathit{tmp}\lt k\)。那么对于每个 \(r\)，\(l\) 是它能延展到的左边界，由于正整数乘积的单调性，此时以 \(r\) 为右端点的满足题目条件的区间个数为 \(r-l+1\) 个。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
  long long ji = 1ll, ans = 0;
  int l = 0;
  for (int i = 0; i < nums.size(); ++i) {
    ji *= nums[i];
    while (l <= i && ji >= k) ji /= nums[l++];
    ans += i - l + 1;
  }
  return ans;
}

使用双指针维护区间信息也可以与其他数据结构比如差分、单调队列、线段树、主席树等等结合使用。另外将双指针技巧融入算法的还有莫队，莫队中将询问离线排序后，一般也都是用两个指针记录当前要处理的区间，随着指针一步步移动逐渐更新区间信息。

例题 2

接下来看一道在树上使用双指针并结合树上差分的例题：

过程

从根开始用 dfs 遍历整棵树，使用一个栈来记录根到当前节点的树链，设一个指针 \(u\) 指向当前节点，另一个指针 \(p\) 指向与 \(u\) 距离不大于 \(t\) 的节点中深度最小的节点。记录到根的距离，每次二分查找确定 \(p\)。此时 \(u\) 对 \(p\) 到 \(u\) 路径上的所有节点都有一个贡献，可以用树上差分来记录。
注意不能直接暴力移动 \(p\)，否则时间复杂度可能会退化至 \(O(n^2)\)。

子序列匹配

过程

此类问题需要将字符串 \(s\) 与 \(t\) 进行匹配，判断 \(t\) 是否为 \(s\) 的子序列。解决这种问题只需先将两个指针一个 \(i\) 放在 \(s\) 开始位置，一个 \(j\) 放在 \(t\) 开始位置，如果 \(s[i]=t[j]\) 说明 \(t\) 的第 \(j\) 位已经在 \(s\) 中找到了第一个对应，可以进而检测后面的部分了，那么 \(i\) 和 \(j\) 同时加一。如果上述等式不成立，则 \(t\) 的第 \(j\) 位仍然没有被匹配上，所以只给 \(i\) 加一，在 \(s\) 的后面部分再继续寻找。最后，如果 \(j\) 已经移到了超尾位置，说明整个字符串都可以被匹配上，也就是 \(t\) 是 \(s\) 的一个子序列，否则不是。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

string findLongestWord(string s, vector<string>& dictionary) {
  sort(dictionary.begin(), dictionary.end());
  int mx = 0, r = 0;
  string ans = "";
  for (int i = dictionary.size() - 1; i >= 0; i--) {
    r = 0;
    for (int j = 0; j < s.length(); ++j) {
      if (s[j] == dictionary[i][r]) r++;
    }
    if (r == dictionary[i].length()) {
      if (r >= mx) {
        mx = r;
        ans = dictionary[i];
      }
    }
  }
  return ans;
}

这种两个指针指向不同对象然后逐步进行比对的方法还可以用在一些 dp 中。

利用序列有序性

很多时候在序列上使用双指针之所以能够正确地达到目的，是因为序列的某些性质，最常见的就是利用序列的有序性。

过程

这种问题也是双指针的经典应用了，虽然二分也很方便，但时间复杂度上多一个 \(\log{n}\)，而且代码不够简洁。

接下来介绍双指针做法：既然要找到两个数，且这两个数不能在同一位置，那其位置一定是一左一右。由于两数之和固定，那么两数之中的小数越大，大数越小。考虑到这些性质，那我们不妨从两边接近它们。

首先假定答案就是 1 和 n，如果发现 \(num[1]+num[n]\gt \mathit{target}\)，说明我们需要将其中的一个元素变小，而 \(\mathit{num}[1]\) 已经不能再变小了，所以我们把指向 \(n\) 的指针减一，让大数变小。

同理如果发现 \(num[1]+num[n]\lt \mathit{target}\)，说明我们要将其中的一个元素变大，但 \(\mathit{num}[n]\) 已经不能再变大了，所以将指向 1 的指针加一，让小数变大。

推广到一般情形，如果此时我们两个指针分别指在 \(l,r\) 上，且 \(l\lt r\), 如果 \(num[l]+num[r]\gt \mathit{target}\)，就将 \(r\) 减一，如果 \(num[l]+num[r]\lt \mathit{target}\)，就将 \(l\) 加一。这样 \(l\) 不断右移，\(r\) 不断左移，最后两者各逼近到一个答案。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

vector<int> twoSum(vector<int>& numbers, int target) {
  int r = numbers.size() - 1, l = 0;
  vector<int> ans;
  ans.clear();
  while (l < r) {
    if (numbers[l] + numbers[r] > target)
      r--;
    else if (numbers[l] + numbers[r] == target) {
      ans.push_back(l + 1), ans.push_back(r + 1);
      return ans;
    } else
      l++;
  }
  return ans;
}

在归并排序中，在 \(O(n+m)\) 时间内合并两个有序数组，也是保证数组的有序性条件下使用的双指针法。

在单向链表中找环

过程

在单向链表中找环也是有多种办法，不过快慢双指针方法是其中最为简洁的方法之一，接下来介绍这种方法。

首先两个指针都指向链表的头部，令一个指针一次走一步，另一个指针一次走两步，如果它们相遇了，证明有环，否则无环，时间复杂度 \(O(n)\)。

如果有环的话，怎么找到环的起点呢？

我们列出式子来观察一下，设相遇时，慢指针一共走了 \(k\) 步，在环上走了 \(l\) 步（快慢指针在环上相遇时，慢指针一定没走完一圈）。快指针走了 \(2k\) 步，设环长为 \(C\)，则有

第一次相遇时 \(n\) 取最小正整数 1。也就是说 \(k=C\)。那么利用这个等式，可以在两个指针相遇后，将其中一个指针移到表头，让两者都一步一步走，再度相遇的位置即为环的起点。

习题

leetcode 15. 三数之和

leetcode 1438. 绝对差不超过限制的最长连续子数组

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用