Two Pointer 左右指標篇 – 陪你刷題

Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。

今天要來探討的是 Two Pointer 雙指標的技巧,其中雙指標又可以分為快慢指標與左右指標,本篇將著重於左右指標。

何謂左右指標

如果想要透過走訪 array 來解決問題,一般會透過 index 或是利用指標由頭走到尾。

在某些狀況會希望由頭跟尾一起出發來走訪,此時透過左右指標分別由 array 的兩端開始,進行搬移或比較兩個元素的動作。

利用左右指標可以解決以下問題:

  1. 反轉 array
  2. 檢查 string 是否回文
  3. 在 array 中找出指定兩數之和
  4. binary search 就是左右指標的一種實現
  5. sliding window

反轉 array

將一個 string 整個反轉,例如 string 是 h e l l o ,反轉後變為 o l l e h ,這是很典型的左右指標搬移應用,若是題目沒有要求空間複雜度在 O(1) 下的話,可以透過宣告一塊空間來存放翻轉後的結果,但有左右指標的幫助,可以輕易的 in-place 就完成翻轉。

Leetcode 對應題目 #344

void reverseString(vector<char>& s) {
    int left = 0;
    int right = s.size()-1;
    while(left < right)
    {
        swap(s[left], s[right]);
        left++;
        right--;
    }
}

檢查 string 是否回文

檢查 string 是否回文,同樣直覺的想到透過左右指標進行比較,也不必耗費多餘空間。

  • Leetcode 對應題目 #125

在 Array 中找出指定兩數之和

Leetcode #167 就是典型的左右指標的應用,題目給你的是排序過的陣列,使用左右指標技巧尋找目標值,時間複雜度可在 O(n) 。

  • 延伸 Leetcode 對應題目 #15, #16

Sliding window

請看 Sliding Window - 陪你刷題

總結

左右指標技巧用於想從頭跟尾同時出發的問題,尤其題目要求做到 in-place ( Space Complexity 為 O(1) ) 時,就可以使用左右指標技巧,必須注意的是處理的資料必須要排序過,否則使用雙指標技巧就沒意義。

延伸閱讀

  1. Two Pointer 快慢指標篇 - 陪你刷題
  2. Sliding Window - 陪你刷題

參考資料

  1. [Leetcode Explore] Two-pointer Technique - Scenario I
  2. 雙指針技巧匯總 - labuladong