跳转至

雙指針

本頁面將簡要介紹雙指針。

引入

雙指針是一種簡單而又靈活的技巧和思想，單獨使用可以輕鬆解決一些特定問題，和其他算法結合也能發揮多樣的用處。

雙指針顧名思義，就是同時使用兩個指針，在序列、鏈表結構上指向的是位置，在樹、圖結構中指向的是節點，通過或同向移動，或相向移動來維護、統計信息。

接下來我們來看雙指針的幾個具體使用方法。

維護區間信息

如果不和其他數據結構結合使用，雙指針維護區間信息的最簡單模式就是維護具有一定單調性，新增和刪去一個元素都很方便處理的信息，就比如正數的和、正整數的積等等。

例題 1

例題 1 leetcode 713. 乘積小於 K 的子數組

給定一個長度為 \(n\) 的正整數數組 \(\mathit{nums}\) 和整數 \(k\), 找出該數組內乘積小於 \(k\) 的連續子數組的個數。\(1 \leq n \leq 3 \times 10^4, 1 \leq nums[i] \leq 1000, 0 \leq k \leq 10^6\)

過程

設兩個指針分別為 \(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

接下來看一道在樹上使用雙指針並結合樹上差分的例題：

例題 2 luogu P3066 Running Away From the Barn G

給定一顆 \(n\) 個點的有根樹，邊有邊權，節點從 1 至 \(n\) 編號，1 號節點是這棵樹的根。再給出一個參數 \(t\)，對於樹上的每個節點 \(u\)，請求出 \(u\) 的子樹中有多少節點滿足該節點到 \(u\) 的距離不大於 \(t\)。數據範圍：\(1\leq n \leq 2\times 10^5,1 \leq t \leq 10^{18},1 \leq p_i \lt i,1 \leq w_i \leq 10^{12}\)

過程

從根開始用 dfs 遍歷整棵樹，使用一個棧來記錄根到當前節點的樹鏈，設一個指針 \(u\) 指向當前節點，另一個指針 \(p\) 指向與 \(u\) 距離不大於 \(t\) 的節點中深度最小的節點。記錄到根的距離，每次二分查找確定 \(p\)。此時 \(u\) 對 \(p\) 到 \(u\) 路徑上的所有節點都有一個貢獻，可以用樹上差分來記錄。
注意不能直接暴力移動 \(p\)，否則時間複雜度可能會退化至 \(O(n^2)\)。

子序列匹配

例題 3 leetcode 524. 通過刪除字母匹配到字典裏最長單詞

給定一個字符串 \(s\) 和一個字符串數組 \(\mathit{dictionary}\) 作為字典，找出並返回字典中最長的字符串，該字符串可以通過刪除 \(s\) 中的某些字符得到。

過程

此類問題需要將字符串 \(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 中。

利用序列有序性

很多時候在序列上使用雙指針之所以能夠正確地達到目的，是因為序列的某些性質，最常見的就是利用序列的有序性。

例題 4 leetcode 167. 兩數之和 II - 輸入有序數組

給定一個已按照 升序排列 的整數數組 numbers，請你從數組中找出兩個數滿足相加之和等於目標數 target。

過程

這種問題也是雙指針的經典應用了，雖然二分也很方便，但時間複雜度上多一個 \(\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\)，則有

\[ \begin{align} & \ 2 k=n \times C+l+(k-l) \\ & \ k=n \times C \\ \end{align} \]

第一次相遇時 \(n\) 取最小正整數 1。也就是説 \(k=C\)。那麼利用這個等式，可以在兩個指針相遇後，將其中一個指針移到表頭，讓兩者都一步一步走，再度相遇的位置即為環的起點。

習題

leetcode 15. 三數之和

leetcode 1438. 絕對差不超過限制的最長連續子數組

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用