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

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

在程式設計領域中,陣列(Array)是一種常見的資料結構,許多經典算法問題都與陣列操作相關。其中,左右指標(Two Pointers)技術是一種高效解決陣列問題的策略,尤其適用於排序陣列。

何謂左右指標

左右指標技術使用兩個指標left和right,分別指向陣列的第一個和最後一個元素。根據具體問題,我們可以讓兩個指標相向移動,在移動過程中執行一些操作,比如交換元素值、計算和值等。

該技術通常可以大幅降低時間和空間複雜度,常見於數組的反轉、回文檢測、兩數之和等經典問題中。

以下是一些典型的左右指標技術應用場景:

反轉 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 - 陪你刷題

左右指標技術的使用條件

需要注意的是,左右指標技術通常需要數組是排序的,否則使用雙指標並無太大意義。因為排序使得我們可以根據元素的遞增(或遞減)關係來調整指標的移動策略。
此外,還需要限制指標的移動範圍,以防止指標在陣列邊界外造成錯誤。一種常見的做法是在指標移動前進行 left < right 的檢查。

總結

左右指標技術是一種優雅且高效的數組操作手段,可以在保證正確性的前提下,有效降低時間和空間複雜度。掌握這一技術有助於我們更好地解決各種數組相關的算法問題,希望通過本文的介紹,您能夠更深入地理解和運用這種思路。

延伸閱讀

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

參考資料

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

Updated on 2024-05-18 22:52:57 星期六