數(shù)組上的雙指針使用 Two Pointers

視頻一：同向雙指針 簡潔模板【基礎(chǔ)算法精講 01】

視頻二：兩數(shù)之和 三數(shù)之和【基礎(chǔ)算法精講 02】

視頻三：盛最多水的容器 接雨水【基礎(chǔ)算法精講 03】

同向雙指針

????靈神說一般把“窗口大小不固定的叫做雙指針，窗口大小固定的叫滑動窗口”，我覺得十分合理。雙指針的題目關(guān)鍵在于從右端點開始遍歷枚舉，這不僅免除了一些判斷的細節(jié)，模版也十分通用。當然這樣的由雙指針指向的子數(shù)組一般需要滿足某種單調(diào)性，具體常常體現(xiàn)在數(shù)組元素都是正數(shù)這樣的題設(shè)條件上。

????這道209題中規(guī)中矩，主要是適應一下這種模版的書寫方式。

????這題稍微麻煩點，主要是當一個子數(shù)組合法時，以該子數(shù)組右端點合法子數(shù)組一共有right-left+1個，這一點如果一開始就是枚舉右端點的話，應該不難想到。其他沒什么意思。

????這題換湯不換藥，多了個hashMap用于快速獲取子串內(nèi)的個元素的出現(xiàn)頻率。

????這題是打周賽的時候遇到的，也是看到了靈神的題解廣告才去的他B站開始看視頻。這題我感覺有點難吧。。。如果要是之前沒有接觸過該類模版，比賽時我這腦子鬼TM想的出來喔！

相向雙指針

????和同向雙指針不同，相向雙指針的題一般需要先對數(shù)組經(jīng)過排序。在一個有序的數(shù)組里找答案，為了節(jié)省時間復雜度，有時可以通過左右指針相向逼近去做，相遇時停止。

????這題有雙指針思維的應該很容易想到。

????兩個時間優(yōu)化可以不加，稍微慢點。主要是除重，之前都是用set做，這里直接除，空間復雜度更好一些吧。我感覺沒必要，就是練練相向雙指針技巧。兩數(shù)之和，三數(shù)之和，四數(shù)之和之前微軟模擬面試的時候，媽的一起模擬的好多人都是假裝思考，然后秒出答案，題都做爛了，沒意思。

????這題應用同樣的木桶思想可以求出，不過接雨水都接魔怔了，很多解法，單調(diào)棧啥的，寫過就忘，傻比一樣沒意思。這里記錄一下。第二種用滾動數(shù)組優(yōu)化了下，空間效率好點。靈神tql...