不少小夥伴看到Array這個標題，應該會想「這也太基礎了吧」，其實這確實是算法中最常見的一種了，這種類型的題目變化比較多，容易結合其他的知識點一起考察，比如字符串、two pointers等這些內容，因為數組這種數據結構是最常用的了，所以才會變化多端、結合複雜的算法一起考察，所以還是需要多加注意。
Sorted Array
Two Pointers
Two sum, 3Sum, 4Sum
Partition Array
1. Sorted Array
有序的數組Sun君認為還是比較有意思的，因為能想到的套路就只有那麼多，其實還是考察你對有序數的一個掌握程度吧。多的不說，先來一個熱身的題目：
Merge Two Sorted Array
合併兩個排序的整數數組A和B變成一個新的數組。
樣例
給出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]
這裡就不用多說了，因為vector的大小是一開始設定好的，所以我們需要開闢一個新的數組來存儲兩個的和，這裡就從最後一個位置開始，代碼如下:
當然了，面試的時候應該不會考這麼簡單的題。相關的題目還有一些，比如將一個小數組歸併到大數組裡面：這個題就不需要再開闢新的數組了，因為A的空間足夠存放B，所以就直接從後面往前比較遍歷就好。比較簡單就不加代碼了。
接下來是一個面經題：
Intersection of Two Arrays
返回兩個數組的交
樣例
nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].
這道題目有很多種做法，比如hash map，排序+合併等，這裡我就用排序+合併的方法來做一下。代碼如下:
這個題目主要是注意代碼簡潔，其他也沒什麼多說的。
到這裡你一定會覺得很簡單，那麼下面一個題還是值得好好分析的：
Median of Two Sorted Arrays
兩個排序的數組A和B分別含有m和n個數，找到兩個排序數組的中位數，要求時間複雜度應為O(log (m+n))。
樣例
給出數組A = [1,2,3,4,5,6] B = [2,3,4,5]，中位數3.5
給出數組A = [1,2,3] B = [4,5]，中位數 3
當然這道題也可以先排序，然後再找中位數，不過這樣的做法是O(nlogn)的，不滿足題目的要求。看到 O(log L) 這樣的複雜度，而且還是有序數組，能想到哪個算法嗎？沒錯，就是二分查找！
要找中位數，就是要找第 k 大的數（k = (L / 2 + 1)，其中L 是上面提到的合併後新數組的長度，當 L 是偶數時，要求第 (L / 2) 大和第 (L / 2 + 1) 大的兩個數）。當我們捨棄掉一部分，假設捨棄部分的長度為 length，那麼接下來就是在剩下的數組裡求第 (k - length) 大的數。逐層縮小範圍，直到兩數組其中一個走完，或者要求的是第 1 大的元素，就可以直接返回結果了。
那如何「選擇」要捨棄哪部分呢？既然是要找合併後的數組 C 的第 k 大元素，即 C[k-1]，那如果我們從 A 和 B 中分別取前 k/2 個元素，其中必然有一部分是是在數組 C 的前 k 個數裡。設 mid = k / 2，當 A[mid - 1] < B[mid - 1] 時，可以斷定 A 的前 mid 個元素是在 C 的前 k 個數裡（此處可用反證法得證），那麼我們則捨棄 A 的前 mid 個元素。反之則捨棄 B 的前 mid 個元素。現在數組 A 或者 B 已經捨棄掉 k/2 個元素，縮小查找範圍了，那接下來可以按照同樣的方法繼續選擇嗎？當然！現在剩下總共 (L - mid) 個元素，且 A 和 B 依舊有序，要找的是第 (k - mid) 大的元素，所以我們可以按照上面的方法繼續遞歸選擇下去，直到找到目標元素。代碼如下：
2. Two Pointers
說到兩個指針系列，那麼最最最重要的題目應該想到的就是Two Sum了，相信應該沒有同學不會吧？題目大意就是給你一個數組，然後找到兩個數之和等於一個target。這個題目的話，不管用hashmap的方法還是排序以後再操作的方法，都是很不錯的思路，就看面試的時候面試官如何要求了。下面是Two Sum用hashmap的實現方法：
那麼我們就直接來說3Sum這個題目吧。
3Sum
給出一個有n個整數的數組S，在S中找到三個整數a, b, c，找到所有使得a + b + c = 0的三元組。
注意：
在三元組(a, b, c)，要求a <= b <= c。
結果不能包含重複的三元組。
有了Two Sum作為鋪墊，3Sum也不會很難了，首先想到hashmap的方法，也是可以做的，不過這裡還是要重點說一下排序以後的方法。
我們要找三個數的和為0，想想可不可以把這個題目轉化為找兩個數，加起來的和等於數組中某個數的取負？這樣就比較好做了，那麼我們可以先對數組進行排序，然後找到一個確定的數，以它的取負作為target，然後在它之後尋找兩個數的和等於這個target，這裡就可以用到兩個指針的方法。代碼如下：
有了3Sum，那麼肯定就有4Sum，這個就不難了。找到i和j，然後在之後進行同樣的two pointer方法，代碼如下：
那麼之後的KSum我覺得大家可以自己想想，然後可以給公眾號留言和Sun君討論。
說完了Sum系列，該說一個比較重要的部分了，也是面試非常非常非常容易考到的問題，就是partition array，不管你是在做快速排序、快速選擇等，都需要用到這個內容。就是把數組變成兩個部分，請大家一定要背誦並默寫，題目如下：
Partition Array
給出一個整數數組 nums 和一個整數 k。劃分數組（即移動數組 nums 中的元素），使得：
所有小於k的元素移到左邊
所有大於等於k的元素移到右邊
返回數組劃分的位置，即數組中第一個位置 i，滿足 nums[i] 大於等於 k。
這個就是使用了當初學習快速排序的思想，多的就不介紹了，如果還是沒有掌握的小夥伴可以自行學習一下。代碼如下：
總結
雖說只是簡簡單單的數組，但還是蘊含了巨大的能量。需要大家多去思考，結合別的數據結構和算法來思考。