第一期講義-雙指針 · ttttt

# 第一期講義-雙指針 # 【91算法-基礎篇】05.雙指針力扣加加，一個努力做西湖區最好的算法題解的團隊。就在今天它給大家帶來了《91 天學算法》，幫助大家擺脫困境，征服算法。 ![](https://img.kancloud.cn/69/70/6970cc286e4e129916d46ce2e0c43d15_1087x1080.jpg) ## 什么是雙指針顧名思議，雙指針就是**兩個指針**，但是不同于 C，C++中的指針，其是一種**算法思想**。如果說，我們迭代一個數組，并輸出數組每一項，我們需要一個指針來記錄當前遍歷的項，這個過程我們叫單指針（index）的話。 ``` <pre class="calibre18">``` for(int i = 0;i < nums.size(); i++) { 輸出(nums[i]); } ``` ``` ![](https://img.kancloud.cn/17/8c/178cf0629fa1dfa1c6e12aee899a5a75_370x633.jpg) （圖 1）那么雙指針實際上就是有兩個這樣的指針，最為經典的就是二分法中的左右雙指針啦。 ``` <pre class="calibre18">``` int l = 0; int r = nums.size() - 1; while (l < r) { if(一定條件) return 合適的值，一般是 l 和 r 的中點 if(一定條件) l++ if(一定條件) r-- } // 因為 l == r，因此返回 l 和 r 都是一樣的 return l ``` ``` ![](https://img.kancloud.cn/c5/95/c595c4acf44f3dfdb09d07e554735454_257x174.jpg) （圖 2）讀到這里，你發現雙指針是一個很寬泛的概念，就好像數組，鏈表一樣，其類型會有很多很多，比如二分法經常用到`左右端點雙指針`。滑動窗口會用到`快慢指針和固定間距指針`。因此雙指針其實是一種綜合性很強的類型，類似于數組，棧等。但是我們這里所講述的雙指針，往往指的是某幾種類型的雙指針，而不是“只要有兩個指針就是雙指針了”。 > 有了這樣一個**算法框架**，或者算法思維，有很大的好處。它能幫助你理清思路，當你碰到新的問題，在腦海里進行搜索的時候，**雙指針**這個詞就會在你腦海里閃過，閃過的同時你可以根據**雙指針**的所有套路和這道題進行**窮舉匹配**，這個思考解題過程本來就像是算法，我會在進階篇《搜索算法》中詳細闡述。那么究竟我們算法中提到的雙指針指的是什么呢？我們一起來看下算法中雙指針的常見題型吧。 ## 常見題型有哪些？這里我將其分為三種類類型，分別是： 1. 快慢指針（兩個指針步長不同） 2. 左右端點指針（兩個指針分別指向頭尾，并往中間移動，步長不確定） 3. 固定間距指針（兩個指針間距相同，步長相同） > 上面是我自己的分類，沒有參考別人。可以發現我的分類標準已經覆蓋了幾乎所有常見的情況。大家在平時做題的時候一定要養成這樣的習慣，將題目類型進行總結，當然這個總結可以是別人總結好的，也可以是自己獨立總結的。不管是哪一種，都要進行一定的消化吸收，把它們變成真正屬于自己的知識。不管是哪一種雙指針，只考慮雙指針部分的話，由于最多還是會遍歷整個數組一次，因此時間復雜度取決于步長，如果步長是 1，2 這種常數的話，那么時間復雜度就是 O(N)，如果步長是和數據規模有關（比如二分法），其時間復雜度就是 O(logN)。并且由于不管規模多大，我們都只需要最多兩個指針，因此空間復雜度是 O(1)。下面我們就來看看雙指針的常見套路有哪些。 ## 常見套路 ### 快慢指針 1. 判斷鏈表是否有環這里給大家推薦兩個非常經典的題目，一個是力扣 287 題，一個是 142 題。其中 142 題我在我的 LeetCode 題解倉庫中的每日一題板塊出過，并且給了很詳細的證明和解答。而 287 題相對不直觀，比較難以想到，這道題曾被官方選定為每日一題，也是相當經典的。 - [287. 尋找重復數](https://leetcode-cn.com/problems/find-the-duplicate-number/) - [【每日一題】- 2020-01-14 - 142. 環形鏈表 II · Issue #274 · azl397985856/leetcode](https://github.com/azl397985856/leetcode/issues/274) - 讀寫指針。典型的是`刪除重復元素` 這里推薦我倉庫中的一道題，我這里寫了一個題解，橫向對比了幾個相似題目，并剖析了這種題目的本質是什么，讓你看透題目本質，推薦閱讀。 - [80.刪除排序數組中的重復項 II](https://github.com/azl397985856/leetcode/blob/master/problems/80.remove-duplicates-from-sorted-array-ii.md) ## 左右端點指針 1. 二分查找。二分查找會在專題篇展開，這里不多說，大家先知道就行了。 1. 暴力枚舉中“從大到小枚舉”（剪枝）一個典型的題目是我之前參加官方每日一題的時候給的一個解法，大家可以看下。這種解法是可以 AC 的。同樣地，這道題我也給出了三種方法，幫助大家從多個緯度看清這個題目。強烈推薦大家做到一題多解。這對于你做題很多幫助。除了一題多解，還有一個大招是多題同解，這部分我們放在專題篇介紹。 [find-the-longest-substring-containing-vowels-in-even](https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solution/qian-zhui-he-zhuang-tai-ya-suo-pythonjava-by-fe-lu/) 1. 有序數組。區別于上面的二分查找，這種算法指針移動是連續的，而不是跳躍性的，典型的是 LeetCode 的`兩數和`，以及`N數和`系列問題。 ## 固定間距指針 1. 一次遍歷（One Pass）求鏈表的中點 2. 一次遍歷（One Pass）求鏈表的倒數第 k 個元素 3. 固定窗口大小的滑動窗口 ## 模板(偽代碼) 我們來看下上面三種題目的算法框架是什么樣的。這個時候我們沒必要糾結具體的語言，這里我直接使用了偽代碼，就是防止你掉進細節。當你掌握了這種算法的細節，就應該找幾個題目試試。一方面是檢測自己是否真的掌握了，另一方面是“細節”，”細節“是人類，尤其是軟件工程師最大的敵人，畢竟我們都是`差不多先生`。 1. 快慢指針 ``` <pre class="calibre18">``` l = 0 r = 0 while 沒有遍歷完 if 一定條件 l += 1 r += 1 return 合適的值 ``` ``` 1. 左右端點指針 ``` <pre class="calibre18">``` l = 0 r = n - 1 while l < r if 找到了 return 找到的值 if 一定條件1 l += 1 else if 一定條件2 r -= 1 return 沒找到 ``` ``` 1. 固定間距指針 ``` <pre class="calibre18">``` l = 0 r = k while 沒有遍歷完自定義邏輯 l += 1 r += 1 return 合適的值 ``` ``` ## 題目推薦如果你`差不多`理解了上面的東西，那么可以拿下面的題練練手。Let's Go! ### 左右端點指針 - 16.3Sum Closest (Medium) - 713.Subarray Product Less Than K (Medium) - 977.Squares of a Sorted Array (Easy) - Dutch National Flag Problem > 下面是二分類型 - 33.Search in Rotated Sorted Array (Medium) - 875.Koko Eating Bananas（Medium） - 881.Boats to Save People（Medium） ### 快慢指針 - 26.Remove Duplicates from Sorted Array（Easy） - 141.Linked List Cycle (Easy) - 142.Linked List Cycle II（Medium） - 287.Find the Duplicate Number（Medium） - 202.Happy Number (Easy) ### 固定間距指針 - 1456.Maximum Number of Vowels in a Substring of Given Length（Medium） > 固定窗口大小的滑動窗口見專題篇的滑動窗口專題（暫未發布） ## 其他有時候也不能太思維定式，比如 <https://leetcode-cn.com/problems/consecutive-characters/> 這道題根本就沒必要雙指針什么的。再比如：<https://lucifer.ren/blog/2020/05/31/101.symmetric-tree/>