Array 總結
source:: 代码随想录
#clippings
數組理論基礎
數組是非常基礎的數據結構，在面試中，考察數組的題目一般在思維上都不難，主要是考察對代碼的掌控能力
也就是說，想法很簡單，但實現起來 可能就不是那麼回事了。
首先要知道數組在內存中的存儲方式，這樣才能真正理解數組相關的面試題
**數組是存放在連續內存空間上的相同類型數據的集合。**數組可以方便的通過下標索引的方式獲取到下標下對應的數據。
舉一個字符數組的例子，如圖所示：
需要兩點注意的是
- 數組下標都是從0開始的。
- 數組內存空間的地址是連續的
正是因為數組的在內存空間的地址是連續的，所以我們在刪除或者增添元素的時候，就難免要移動其他元素的地址。
例如刪除下標為3的元素，需要對下標為3的元素後面的所有元素都要做移動操作，如圖所示：
而且大家如果使用C++的話，要注意vector 和array的區別，vector的底層實現是array，嚴格來講vector是容器，不是數組。
數組的元素是不能刪的，只能覆蓋。
那麼二維數組直接上圖，大家應該就知道怎麼回事了
那麼二維數組在內存的空間地址是連續的麼？
我們來舉一個Java的例子，例如： int[][] rating = new int[3][4]; ， 這個二維數組在內存空間可不是一個 3*4 的連續地址空間
看了下圖，就應該明白了：
所以Java的二維數組在內存中不是 3*4 的連續地址空間，而是四條連續的地址空間組成！
在面試中，數組是必考的基礎數據結構。
其實數組的題目在思想上一般比較簡單的，但是如果想高效，並不容易。
我們之前一共講解了四道經典數組題目，每一道題目都代表一個類型，一種思想。
二分法
數組：每次遇到二分法，都是一看就會，一寫就廢 (opens new window)
這道題目呢，考察數組的基本操作，思路很簡單，但是通過率在簡單題裡並不高，不要輕敵。
可以使用暴力解法，通過這道題目，如果追求更優的算法，建議試一試用二分法，來解決這道題目
- 暴力解法時間複雜度：O(n)
- 二分法時間複雜度：O(logn)
在這道題目中我們講到了循環不變量原則，只有在循環中堅持對區間的定義，才能清楚的把握循環中的各種細節。
二分法是算法面試中的常考題，建議通過這道題目，鍛煉自己手撕二分的能力。
雙指針法
雙指針法（快慢指針法）：通過一個快指針和慢指針在一個for循環下完成兩個for循環的工作。
- 暴力解法時間複雜度：O(n^2)
- 雙指針時間複雜度：O(n)
這道題目迷惑了不少同學，糾結於數組中的元素為什麼不能刪除，主要是因為以下兩點：
- 數組在內存中是連續的地址空間，不能釋放單一元素，如果要釋放，就是全釋放（程式運行結束，回收內存棧空間）。
- C++中vector和array的區別一定要弄清楚，vector的底層實現是array，封裝後使用更友好。
雙指針法（快慢指針法）在數組和鏈表的操作中是非常常見的，很多考察數組和鏈表操作的面試題，都使用雙指針法。
滑動窗口
本題介紹了數組操作中的另一個重要思想：滑動窗口。
- 暴力解法時間複雜度：O(n^2)
- 滑動窗口時間複雜度：O(n)
本題中，主要要理解滑動窗口如何移動 窗口起始位置，達到動態更新窗口大小的，從而得出長度最小的符合條件的長度。
滑動窗口的精妙之處在於根據當前子序列和大小的情況，不斷調節子序列的起始位置。從而將O(n^2)的暴力解法降為O(n)。
如果沒有接觸過這一類的方法，很難想到類似的解題思路，滑動窗口方法還是很巧妙的。
模擬行為
模擬類的題目在數組中很常見，不涉及到什麼算法，就是單純的模擬，十分考察大家對代碼的掌控能力。
在這道題目中，我們再一次介紹到了循環不變量原則，其實這也是寫程式中的重要原則。
相信大家有遇到過這種情況： 感覺題目的邊界調節超多，一波接著一波的判斷，找邊界，拆了東牆補西牆，好不容易運行通過了，代碼寫的十分宂餘，毫無章法，其實真正解決題目的代碼都是簡潔的，或者有原則性的，大家可以在這道題目中體會到這一點。
這個圖是 代碼隨想錄知識星球 (opens new window) 成員：海螺人 (opens new window)，所畫，總結的非常好，分享給大家。
從二分法到雙指針，從滑動窗口到螺旋矩陣，相信如果大家真的認真做了「代碼隨想錄」每日推薦的題目，定會有所收獲。
推薦的題目即使大家之前做過了，再讀一遍文章，也會幫助你提煉出解題的精髓所在。