更多面試題請關(guān)注頭條號皮璧、微信號： itworld123
數(shù)組是所有數(shù)據(jù)結(jié)構(gòu)中最簡單的數(shù)據(jù)結(jié)構(gòu)了疑俭，很多復雜的數(shù)據(jù)結(jié)構(gòu)依賴數(shù)組實現(xiàn)，比如哈希表等伍玖。數(shù)組是一個連續(xù)的內(nèi)存空間，因此我們可以一次定位其中的元素窍箍，也就是其查找是O(1)時間復雜度旷祸。
因此，數(shù)組相關(guān)的面試題也是最多的姻乓。很多面試官喜歡問數(shù)組相關(guān)的面試題五辽，如果大家上力扣就會發(fā)現(xiàn)數(shù)組面試題是最多的。這主要是因為杆逗，數(shù)組的面試題可易，可難罪郊，因此面試起來非常自如。
數(shù)組的面試題歸結(jié)起來其實就是對數(shù)組的各種遍歷和操作尚洽。遍歷就是查找了，核心是二分查找腺毫；操作就是對數(shù)組元素的移動和刪除等操作。下面我們通過幾個經(jīng)典的面試題介紹一下數(shù)組面試題的解法潮酒。
兩數(shù)之和（基本遍歷類）
給定一個整數(shù)數(shù)組array和一個目標值 target睛挚，在該數(shù)組中找出和為目標值的那兩個整數(shù)并返回他們的下標。為了簡化問題急黎，我們可以假設(shè)數(shù)組中只有一對答案扎狱。為了明確問題侧到，我們舉一個具體的例子。假設(shè)數(shù)組為[1, 3, 5, 7], target = 8
在上述數(shù)組中3+5=8淤击，因此返回 [1, 2]匠抗，也就是數(shù)組的下標。
該面試題是一個典型的數(shù)組遍歷類的問題污抬，最簡單暴力的解法是對數(shù)組中的每一個元素進行遍歷配對汞贸，找到合適的結(jié)果。但是這種情況的時間復雜度太高壕吹，通常不能通過面試著蛙。為了讓大家清楚，我們還是介紹一下該算法耳贬。
如圖2所示踏堡，我們逐次遍歷數(shù)組中的元素，并將其與后面的元素進行對比咒劲，判斷是否有符合要求的元素對顷蟆。實現(xiàn)算法如下所示，該算法耗時很長腐魂，大家可以在力扣測試一下帐偎。
另外一種解法是借助哈希表，因為哈希表幾乎可以在O(1)的時間復雜度找到元素蛔屹，因此我們可以通過空間來換時間削樊。具體方法是在遍歷數(shù)組的時候，首先判斷哈希表中是否有可以與當前元素配對的元素兔毒，如果沒有則將該元素加入哈希表中（為后面查找做準備）漫贞，如果有則說明找到了元素對。具體代碼實現(xiàn)如下所示育叁。
移除元素
假設(shè)有一個數(shù)組array迅脐，數(shù)組中的值是不確定的，然后給定目標值target豪嗽。移除數(shù)組中所有值為target的元素谴蔑。最后返回移除滿足要求的元素后的新數(shù)組的長度。附加要求：不使用輔助空間龟梦，僅使用O(1)空間的情況下對原始數(shù)組進行修改完成該題目隐锭。
例如下面一個數(shù)組，假設(shè)目標數(shù)為5计贰，那么直觀的思路是找到該元素之后將后面的所有元素向前移動蹦玫，并覆蓋掉找到的元素即可。
但是上述算法最大的問題是時間復雜度太高，如果數(shù)組很長的話將非常耗時福贞。其實我們可以變換一下挖帘。比如當我們發(fā)現(xiàn)目標元素的時候并不馬上用后面元素覆蓋，而是標記下來逻族；在遍歷后面元素的時候如果后面元素不等于目標元素則將其覆蓋掉標記的元素骄崩，然后將標記后移要拂，以此類推。這就是所謂的雙指針法搏嗡，這是一個通用方法拉一，很多地方可以用到舅踪。具體如圖所示。
有了上述思路悍赢，代碼實現(xiàn)就非常簡單了左权。下面是具體的代碼實現(xiàn)赏迟。
整數(shù)加一（本地操作）
給定一個由整數(shù)組成的非空數(shù)組所表示的非負整數(shù)锌杀，在該數(shù)的基礎(chǔ)上加一。最高位數(shù)字存放在數(shù)組的首位糕再， 數(shù)組中每個元素只存儲單個數(shù)字。假設(shè)除了整數(shù) 0 之外殴蹄，這個整數(shù)不會以零開頭袭灯。下面給出2個具體的例子绑嘹，如圖所示。
在圖5中有2個例子蛤克，上面的例子是整數(shù)135759加1构挤，由于末位是9筋现，因此會進位箱歧。下面這個例子是沒有進位的示例。
下面是一個C語言的代碼實現(xiàn)洒沦，算法比較簡單价淌，這里就不過多介紹了。
數(shù)組面試題集錦
1.盛最多水的容器
2.三數(shù)之和
3.四數(shù)之和
4.搜索旋轉(zhuǎn)排序數(shù)組
5.搜索插入位置
6.最大子序和
7.合并區(qū)間
8.合并兩個有序數(shù)組
9.楊輝三角
10.買賣股票的最佳時機
11.求眾數(shù)
12.旋轉(zhuǎn)數(shù)組
關(guān)于數(shù)組的面試題還很多括尸，本文主要是介紹了一些數(shù)組基本操作的內(nèi)容濒翻。其實還有很多比較復雜的面試題，比如動態(tài)規(guī)劃和回溯等淌喻。相關(guān)內(nèi)容可以參考本專欄的其它專題文章娶眷。
