分類: Leetcode
Sliding Window – 陪你刷題
何謂 sliding window?
sliding window 適用於線性資料結構,可以用來解決在線性資料結構中找到滿足特定條件的 sub-sequence 或 sub-array的問題。
sliding window 有以下特點:
1. 在線性時間內完成
2. 利用 two pointer 來控制 window 大小
3. 答案是連續的資料
Two Pointer 左右指標篇 – 陪你刷題
Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。
今天要來探討的是 Two Pointer 雙指標的技巧,其中雙指標又可以分為快慢指標與左右指標,本篇將著重於左右指標。
何謂左右指標
如果想要透過走訪 array 來解決問題,一般會透過 index 或是利用指標由頭走到尾。
在某些狀況會希望由頭跟尾一起出發來走訪,此時透過左右指標分別由 array 的兩端開始,進行搬移或比較兩個元素的動作。
利用左右指標可以解決以下問題:
- 反轉 array
- 檢查 string 是否回文
- 在 array 中找出指定兩數之和
- binary search 就是左右指標的一種實現
- sliding window
閱讀全文〈Two Pointer 左右指標篇 – 陪你刷題〉