Two pointers —  雙指針

發表於 更新於 分類於
雙指針算是一個解題蠻常用的小技巧，雙指針指的是用兩個指針對整個資料做遍歷，而雙指針又依照移動的方向性，分為對撞指針 — 反方向和快慢指針 — 同方向。

雙指針算是一個解題蠻常用的小技巧，雙指針指的是用兩個指針對整個資料做遍歷，而雙指針又依照移動的方向性，分為對撞指針  —  反方向和快慢指針  —  同方向。

對撞指針

兩個指針為相反方向，通常一個在起點，一個在終點，慢慢向中間靠攏，在起始點的通常命名為 left，在終點是 right，那麼就用經典的 two sum 來示範雙指針吧!

注意  :如果要用雙指針解這題 ，陣列必須要是有依序排列過的

two sum 的題目為給定一個陣列 arr 和目標數 target，arr[x] + arr[y] = target，請回傳 arr[x], arr[y]

Example : 有一個排序過的陣列為[2, 3, 5, 9, 11]，請問陣列中的哪兩個數字相加會等於目標數 8 呢?

實作步驟如下:

  1. 在起點設置左指針，在終點設置右指針

  1. 此時因為 2 + 11 = 13 大於我們的目標數 8， 所以將右指針移動到 9 的位置

  1. 結果 2 + 9 = 11，還是大於 8 ，所以又把右指針移到 5 的位置

  1. 2 + 5 = 7 ，不幸的小於目標數 8 ，所以把左指針移動到 3，這時候就會發現 3 、5 這個組合不就是我們要找的嗎?所以成功找到兩個加起來總和為 8 的數字了!

用 js 實作雙指針

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const twoSum = (arr, target) => {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    if (arr[left] + arr[right] === target) {
      return [arr[left], arr[right]];
    }
    if (arr[left] + arr[right] > target) {
      right--;
    } else {
      left++;
    }
  }
  return null;
};

twoSum([2, 3, 5, 9, 11], 8);

快慢指針

可以想像是程式界的龜兔賽跑，兩個指針的移動方向均為相同方向，但移動的速率為一快一慢。

題目範例:檢查 str2 是否為 str1 的 subSequence，str1 = forever love，str2 = love

實作步驟如下:

  1. 紅色指針是快指針，黃色是慢指針，一開始兩種指針都會在起始點

  1. 快指針每次都會移動一格，慢指針則是必須符合條件才會移動，移動條件:當快指針指向的字母與慢指針相同時

  1. 不幸的因為一直不符合條件，所以只有快指針一路往後走

  1. 好不容易，當快指針指到 l，終於符合條件了!所以慢指針就可以前進一格

  1. 當慢指針指到最後一格的時候，就代表 love 的確是 forever love 的 subSequence

用 js 實作快慢指針

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const isSubsequence = (str1, str2) => {
  if (str1.length === 0) return true;

  let slow = 0;
  let fast = 0;

  while (fast < str2.length) {
    if (str1[slow] === str2[fast]) {
      slow++;
    }
    if (slow >= str1.length) {
      return true;
    }
    fast++;
  }
  return false;
};

isSubsequence("love", "forever love");

快慢指針的解題方法蠻常被運用在 Linked List 的題型上面，像是反轉 Linked List 或是確認該 Linked List 是否有 Cycle(如下圖)