Two Pointer: 低空間複雜度的解題技巧
在這篇文章中，我探討了 Two Pointer 技巧，這是一種用於處理陣列、字符串或連結列表等線性數據結構的算法。通過兩種類型的指針——左右指標和快慢指標，我們可以有效解決諸如合併排序、尋找和判斷回文等問題。這種方法不僅提高了效率，還減少了額外的空間使用，使空間複雜度降低至接近 O(1)。
Two Pointer 是快速查找解題常用技巧，常見於處理 Array 、String 或 Linked-List
在特定的情況下，如已排序資料等，使用 Two Pointer 通常讓執行時間複雜度保持在線性 O(N)，降低運算時間，更能在接近不額外使用空間原地交換值，讓時間複雜度接近 O(1)。
KeyWords: 交換、不額外使用空間、已排序資料
1. Two Pointer 的兩種類型
- 左右指標 (反向指標)
- 指標通常沒有快慢，一個從頭一個從尾開始逐漸靠近，類似 Quick Sort 的 Hoare
- 快慢指標 (同向指標)
- 指標會有快慢之分，都會一起從頭/從尾向右/左移動，類似 Quick Sort 的 Lomuto
左右指標 (反向指標), 圖片來源: Count the Number of Triplets in…
快慢指標 (同向指標), 圖片來源: Basics of Two Pointers Technique
2. Two Pointer 常見題目
- Easy
- Medium
參考資料
1. 【第十天 - Two-pointer 介紹】
2. 演算法筆記系列 — Two Pointer 與Sliding Window
3. Two Pointer 快慢指標篇
4. [LeetCode] 雙指標法(Two pointers)解題
5. 283.[圖解]Move Zeroes
6. LeetCode 刷题进大厂(2)— Two Pointers
7. 【第十天 - Two-pointer 介绍】
8. 【演算法】Two-pointer雙指標