① 演算法面試通關40講 覃超 Leetcode 題目總結（未完待續）
主要是自己收集的題目，正在學習王爭老師的數據與演算法結構之美和覃超老師的演算法面試通關四十講，兩位老師推薦很經典的面試題。所以為了方便自己，在這里做一個匯總。如果對你有幫助那當然好，或者也可以看參考資料，裡面有很多優秀的Github的資源。
參考資料
演算法復雜度查看： https://www.bigocheatsheet.com/
C語言解法推薦： https://github.com/begeekmyfriend/leetcode
Java解法推薦： https://github.com/azl397985856/leetcode
數據結構與演算法之美（王爭）（有各種語言的版本）： https://github.com/wangzheng0822/algo
Github 40K star leetcode： https://github.com/azl397985856/leetcode
Github 13K star Leetcode： https://github.com/haoel/leetcode
Github 63K star 用動畫的形式呈現解LeetCode題目的思路： https://github.com/MisterBooo/LeetCodeAnimation
python 解法： https://github.com/qiyuangong/leetcode
其他解法： https://github.com/qiyuangong/leetcode
06|面試題：反轉一個單鏈表&判斷鏈表是否有環
數據與演算法結構之美：
21 Merge Two Sorted Lists 【 C 】【 python 】
刪除鏈表倒數第 n 個結點 【 Leetcode 的解題 】
求鏈表的中間結點 Middle of the Linked List
20 Valid Parentheses
232 Implement Queue using Stacks 【 C 】【 My C solution 】
225 Implement Stack using Queues 【 C 】
703 Kth Largest Element in a Stream
239 Sliding Window Maximum
242 Valid Anagram
1 Two Sum 【 C 】
15 3Sum
18 4Sum
98 Validate Binary Search Tree
235 Lowest Common Ancestor of a Binary Search Tree
236 Lowest Common Ancestor of a Binary Tree
50 Pow(x, n)
169 Majority Element
122 Best Time to Buy and Sell Stock II
冒泡排序，選擇排序，插入排序，供參考：【 C 】
(未完待續，大概等我做完上面這些就可以繼續補充剩下的了吧）
② 耗時7天我終於把LeetCode刷通關：數組十七連，真是不簡單
大家好，我是老三，一個刷題困難戶，接下來我們開始數組類型演算法的刷題之旅！
數組
數組基本上是我們最熟悉的數據結構了，剛會寫「Hello World」不久，接著就是「楊輝三角」之類的練習。
數組結構
上圖是一個字元數組的例子。
因為內存空間連續，所以可以直接通過下標獲取對應的元素。
但是刪除就麻煩一點，相當於填坑，一個元素被移走，留下的坑，需要其它元素來填上。
刪除元素
在Java中，多維數組的存儲本質上也是一個行優先的一維數組。
我們都知道，在Java中的 「=」 用在基本數據類型上，是值傳遞，用在引用數據類型上，是引用傳遞。
這一塊展開可以寫一篇文章，我們只簡單看個例子：
大家可以看到，newArray改變了，array也跟著變了。
為什麼呢？
在Java中，數組是引用數組類型。array、newArray都是存儲在棧中的引用，它們指向堆中真正存儲的數組對象。
所以改變了newArray，實際是改變了newArray指向的數組。
數組引用傳遞
這一點是我們刷題需要注意的，復制數組需要在循環中一個個復制。
題目：704. 二分查找 (https://leetcode-cn.com/problems/binary-search/)
難度：簡單
描述：
給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
題目示例
思路：
二分查找可以說我們都很熟了。
因為數組是有序的，所以定義三個指針，low、high、mid，每次與中間指針指向的元素nums[mid]比較，
二分查找
但是這個代碼還有一處問題，在哪呢？
int mid = (left + right) / 2;
這個地方可能會因為left和right數值太大導致內存溢出，所以應該寫為 int mid = left + ((right - left) >> 1);
修改之後代碼如下：
時間復雜度：O(logn)
題目：35. 搜索插入位置 (https://leetcode-cn.com/problems/search-insert-position/)
難度：簡單
描述：
給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為 O(log n) 的演算法。
題目示例
思路：
二分查找比較簡單，但寫對還要費點功夫，再做一道基本一樣的題鞏固一下。
這道題基本一樣，插入的位置可能有四種情況：
二叉樹插入位置
代碼如下：
時間復雜度：O(logn)
題目：34. 在排序數組中查找元素的第一個和最後一個位置 (https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
難度：中等
描述：
給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
如果數組中不存在目標值 target，返回 [-1, -1]。
進階：
題目示例
思路：
看到時間復雜度 O(log n) ，數組有序，我們知道，二分查找該上場了。
但是這道題有點不一樣，它需要尋找邊界。
那我們怎麼辦呢？
這就引入了尋找邊界的二分查找。
這道題的思路是什麼呢？
我們分別用二分查找來尋找左邊界和右邊界。
一般的二分查找：
注意，我們這里的返回條件是 nums[mid] == target ，但是尋找邊界的時候就不能這樣了，因為我們不能確定mid是不是我們的邊界。
以尋找左邊界為例，條件是 target <= nums[mid] 的時候，我們接著往左移動。
尋找右邊界也類似。
代碼如下：
時間復雜度：O(logn)
題目：27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)
難度：簡單
描述：
給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等於 val 的元素，並返回移除後數組的新長度。
不要使用額外的數組空間，你必須僅使用 O(1) 額外空間並 原地 修改輸入數組。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。
說明:
為什麼返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對於調用者是可見的。
你可以想像內部操作如下:
思路
「暴力解法」
暴力解法沒什麼好說的，和上道題類似，找到要刪除的元素，把它後面的元素全部向前移動一位。
暴力解法
這里有兩點需要注意：
代碼如下：
時間復雜度：O(n²)。
「雙指針法」
雙指針法，是數組和鏈表題中非常常用的一種方法。
這道題用雙指針法怎麼解決呢？
定義兩個指針，一個前，一個後。沒有找到目標的時候front和after一起移動，找到目標的時候，after停下來，front接著移動，把front指向的值賦給after指向的值。
這樣一來，雙指針就通過一個循環完成了雙循環完成的事情。
雙指針法
代碼如下：
時間復雜度：O(n)。
題目：27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)
難度：簡單
描述：
給你一個有序數組 nums ，請你 原地 刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除後數組的新長度。
不要使用額外的數組空間，你必須在 原地 修改輸入數組 並在使用 O(1) 額外空間的條件下完成。
說明:
為什麼返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對於調用者是可見的。
你可以想像內部操作如下:
題目示例
思路
趁著上一道題勁兒還沒緩過來，趕緊做一道基本一樣的鞏固一下。
直接上代碼：
時間復雜度：O(n)。
題目：283. 移動零 (https://leetcode-cn.com/problems/move-zeroes/)
難度：簡單
描述：
給定一個數組 nums ，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
「示例:」
「說明」 :
思路
繼續沿著上一道題的思路。
移動零
代碼如下：
時間復雜度：O(n)。
題目：977. 有序數組的平方 (https://leetcode-cn.com/problems/squares-of-a-sorted-array/)
難度：簡單
描述：
給你一個按 「非遞減順序」 排序的整數數組 nums ，返回 「每個數字的平方」 組成的新數組，要求也按 「非遞減順序」 排序。
題目示例
思路
「暴力排序法」
這道題一看，最直觀的做法是什麼呢？
先求數字平方的數組，然後再把新數組排序。
代碼也好寫：
時間復雜度：遍歷時間復雜度O(n)，快排時間復雜度O(nlogn)，所以時間復雜度O(n+nlogn)。
思路
「雙指針法」
我們連寫幾道雙指針了，這道題能不能用雙指針實現呢？
我們分析一下，這個數組在取平方之前，是有序的，那麼它絕對值最大的數一定是在兩端的。
所以我們可以定義兩個指針，一個指向最左端，一個指向最右端，比較兩者平方的大小，大的平方放入結果數組，並移動指針。
有序數組的平方
代碼如下：
時間復雜度：O(n)。
題目：1. 兩數之和 (https://leetcode-cn.com/problems/two-sum/)
難度：簡單
描述：給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，並返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。
你可以按任意順序返回答案。
題目示例
思路：
「暴力解法」
上來我們先來個最簡單的暴力解法，大家應該都知道冒泡排序吧，類似的兩層循環。
兩層循環
代碼寫起來也很簡單：
時間復雜度：看到這個雙循環，就知道時間復雜度O(n²)。
「哈希輔助法」
時間復雜度O(n²)多少有點過了，這道題的重點是兩個元素相加之和的判斷。
我們可以用一個Hash集合把元素存起來，這樣一來遍歷一遍就夠了，例如目標和9，當前元素2，只需要判斷集合里是否有元素7就行了。
時間復雜度：從Hash查詢和取值時間復雜度都是O(1)，所以整體時間復雜度是O(1)。
題目：15. 三數之和 (https://leetcode-cn.com/problems/3sum/)
難度：簡單
描述：
給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為0且不重復的三元組。
注意：答案中不可以包含重復的三元組。
題目示例
思路：
「哈希法」
做完兩數之和以後，我們首先想到的就是哈希法。
兩層循環，取到a，b，再通過 0-(a+b) 來確定c。
但是這里還有一個問題， 答案中不可以包含重復的三元組。
所以，我們還要想辦法去掉Hash里的重復元素。
可以加入一個約束，第三個數的索引大於第二個數才存入。
時間復雜度：雙循環，O(n²)。
雖然這么也寫出來了，但是，說實話，很難寫出沒有問題的代碼。
我們寫了這么多雙指針，那麼有沒有可能用雙指針的方式呢？
「雙指針法」
首先對數組進行排序，然後遍歷數組。
然後再在當前節點後面取左右指針，判斷左右指針的值是否等於0-nums[i]，然後分別左右移動。
怎麼去重呢？
滿足條件時，看左指針的值是否和前一個位置相等，右指針的值是否和和它後一個位置的值相等。
雙指針法
代碼如下：
時間復雜度：O(n²)
題目：18. 四數之和 (https://leetcode-cn.com/problems/4sum/)
難度：簡單
描述：
給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復的四元組。
注意：答案中不可以包含重復的四元組。
題目示例
思路：
我們延續三數之和的思路，在三數之和外面再套一層循環。
時間復雜度：O(n³)
題目：209. 長度最小的子數組(https://leetcode-cn.com/problems/minimum-size-subarray-sum/)
難度：中等
描述：
給定一個含有 n 個正整數的數組和一個正整數 target 。
找出該數組中滿足其和 target 的長度最小的 連續子數組 [numsl, numsl+1, ..., numsr-1, numsr] ，並返回其長度。如果不存在符合條件的子數組，返回 0 。
題目示例
思路
這道題是一道經典的滑動窗口問題[4]。
image-20210801164436322
代碼如下：
時間復雜度：O(n)，雖然循環里套循環了，但是starrt和end各自被移動了n次，所以時間復雜度是O(n)。
題目：219. 存在重復元素 II (https://leetcode-cn.com/problems/contains-plicate-ii/)
難度：簡單
描述：
給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，並且 i 和 j 的差的 絕對值 至多為 k。
題目示例
思路：
上面我們做了一道滑動窗口的題，我們接著再做一道也可以用滑動窗口解決的問題。
這道題的滑動窗口略有區別，上一道題的窗口是活動的，這個是 固定的滑動窗口 ,維護一個長度為k的固定窗口，如果窗口內含有目標值，返回。如果窗口進入新的元素，就需要把頭部的元素移除掉，保持窗口的長度。
固定窗口
代碼如下：
時間復雜度：O(n)。
題目：1052. 愛生氣的書店老闆(https://leetcode-cn.com/problems/grumpy-bookstore-owner/)
難度：中等
描述：
今天，書店老闆有一家店打算試營業 customers.length 分鍾。每分鍾都有一些顧客（customers[i]）會進入書店，所有這些顧客都會在那一分鍾結束後離開。
在某些時候，書店老闆會生氣。如果書店老闆在第 i 分鍾生氣，那麼 grumpy[i] = 1，否則 grumpy[i] = 0。當書店老闆生氣時，那一分鍾的顧客就會不滿意，不生氣則他們是滿意的。
書店老闆知道一個秘密技巧，能抑制自己的情緒，可以讓自己連續 X 分鍾不生氣，但卻只能使用一次。
請你返回這一天營業下來，最多有多少客戶能夠感到滿意。
「示例：」
思路：
這道題是一道固定窗口的問題。
整體思路就是把不生氣的部分作為固定窗口，固定窗口把customers分成了三部分，最後求三部分的最大和。
固定窗口
時間復雜度：O(n)。
空間復雜度：O(1)。
題目：面試題3. 數組中重復的數字 (https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)
難度：復雜
描述：
找出數組中重復的數字。
在一個長度為 n 的數組 nums 里的所有數字都在 0 n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。
「示例 1：」
思路：
「哈希法」
這種找重復的數字問題，我們腦子里第一下就想起來，用Hash存儲元素，然後進行比對。
代碼實現也很簡單：
時間復雜度：O(n)。
空間復雜度：O(n)
但今天的主角不是它，而是
「原地置換法」
我們注意到一個條件 所有數字都在 0 n-1 的范圍內 ,那就在這方面進行操作，我們可以把元素放到它的值對應的下標的位置。
例如 num[2]=1，那我們就把它放到下標1的位置。
接著遍歷，元素發現它應該待的坑已經被它的雙胞胎兄弟給佔了，它就知道，它是多餘的那個。
原地置換
代碼如下：
時間復雜度：O(n)。
空間復雜度：O(1)
題目：41. 缺失的第一個正數 (https://leetcode-cn.com/problems/first-missing-positive/)
難度：復雜
描述：
給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。
請你實現時間復雜度為 O(n) 並且只使用常數級別額外空間的解決方案。
題目示例
思路
「輔助數組」
這道題有一個非常巧妙地的辦法！[1]
可以引入一個輔助數組，從1開始，在對應的位置存入原數組對應的元素。如原數組num[0]=1，那麼這個元素就應該存入輔助數組 helper[1]。
然後遍歷輔助數組，發現的第一個坑就是缺失的第一個正數。
輔助數組
代碼如下：
時間復雜度：O(n)。
空間復雜度：O(n)。
「原地置換法」
我們上面用了原地置換法解決了一個問題，降低了空間復雜度，我們這道題是不是也可以呢？
原地置換沒法修改數組長度，我們肯定不能nums[i] 存 i 了，我們左移一下，num[i-1]存i。
原地置換
代碼實現如下：
時間復雜度：O(n)。
空間復雜度：O(1)。
題目：54. 螺旋矩陣 (https://leetcode-cn.com/problems/spiral-matrix/)
難度：中等
描述：
給你一個 m 行 n 列的矩陣 matrix ，請按照 「順時針螺旋順序」 ，返回矩陣中的所有元素。
示例 1：
示例2
思路
這道題，思路比較容易想，就是上右下左四個方向順時針遍歷數組。
順時針遍歷數組
但是這道題的細節是魔鬼。
有兩種，一種是一圈遍歷完成，上下左右的位置移動，遍歷是左閉右開[的條件。
我們採用的是第二種，每遍歷完一條邊，就移動對應的位置，遍歷就是左閉右閉的條件。
還有一點細節就是值得注意的是，遍歷過程中可能會出現出現 top > bottom || left > right ，其中一對邊界彼此交錯了。
這意味著此時所有項都遍歷完了，如果沒有及時 break ，就會重復遍歷。
代碼如下：
時間復雜度：O(mn)，其中 m 和 n 分別是輸入矩陣的行數和列數。
題目：59. 螺旋矩陣 II (https://leetcode-cn.com/problems/spiral-matrix-ii/)
難度：中等
描述：
給你一個正整數 n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。
示例
思路
和上面一道題基本一模一樣，我們往裡面套就行了。
代碼如下：
時間復雜度：O(n²)
劍指 Offer 29. 順時針列印矩陣 也是一道類似的題目。
寫了個順口溜總結一下：