2019最新大廠面試演算法真題解析

如今想要收穫大廠offer，在面試的前幾輪，總是躲不開演算法這座大山。

常聽人說，演算法很難。這話沒錯。演算法本身是是一個艱深的方向。但是演算法題卻有據可循。通過有針對性的學習和練習，我們完全可以掌握解題的基本方法和技巧，見題拆題，掃清通往offer之路上的障礙。

看看手上這些各個大廠的面試演算法真題，我想，不如開始一個新的系列，和大家一起解析真題，學習解題方法，開闊解題思路。頭腦越練習，越靈光。

接下來，就讓我們來看第一題：

題目

解析

初次見到一個問題，如果暫時沒有什麼特別清晰的思路或靈感，不妨安下心來，首先想一想這道題目的暴力解法。

簡單粗暴的暴力解法不考慮效率和美觀，只考慮正確性，所以往往效率較低。但是，通過觀察暴力解法中冗餘或者重複的部分，我們就可以找到進一步優化的切入點，想出更有效率的演算法。

小技巧： 在面試中，如果暫時頭腦空白，想不到漂亮的解法，不妨坦率地用簡潔的話語先描述一下暴力解法，在這個過程中發現思路，找到優化解法。這個過程，也有助於面試官考察你的整體解題思路，還可能給你加分喲

暴力解法

這道題的暴力解法很簡單。

只要將數組中所有數字對求和，然後和給定的數字k相比較，就知道是否有和k相等的值了。

假設數組中有n個數字，將暴力解法寫成偽代碼pseudo code的話，就是這個樣子：

暴力解法使用了兩個嵌套在一起的循環，顯而易見，它的時間複雜度是O(n^2)。為了降低時間複雜度，我們來分析一下暴力解法中冗餘或者重複的部分。

暴力解法試圖對數組中 所有 數字對進行求和操作。

這部分操作是否存在冗餘的部分呢?

我們能不能減少需要查看的數字對的數量呢?

想要對這一點進行優化，我們就要利用題目中的另一個線索，也就是數字k了。

其實這道題目就是在給元素「配對兒」。

對於數組中的任一數字array[i]，如果希望它和它的「另一半」相加之和等於k，那就意味著它的「另一半」的值必須是k-array[i]。

也就是說，只要數組中也存在一個等於k-array[i]的元素，就可以滿足相加等於k這個條件了：

好了，現在我們已經有了進一步優化暴力解法的思路了。

在揭曉優化解法的偽代碼之前，請你先開動腦筋，試著自己把代碼寫出來吧

思考～思考～

優化解法

時間到～下面就是優化演算法的偽代碼了：

在優化演算法中，我們使用了一個map來記錄我們想要尋找的「另一半」的元素，也就是之前例子裡面提到的target

接下來，我們只需要遍歷array一次。

如果array[i]已經和map中的元素相符，就說明array[i]和我們之前遍歷到的某一個元素恰好是相加為k的「一對兒」，演算法直接返回true。

如果不相符，那麼我們就把k-array[i]放進map中去，期待接下來遍歷到的元素能夠和k-array[i]相符。

這個優化演算法只需要遍歷array一次，所以它的時間複雜度只有O(n)。而我們最多也只會將array中所有元素的「另一半」放進map中去，所以演算法的空間複雜度也是O(n)

實現

想出解法只是第一步，為了正確地實現解法，我們還需要考慮實現中的細節。

讓我們想一想這個問題的輸入和輸出：

輸出

這個問題的輸出很簡單，就是一個boolean值，true/false

輸入

題目中對於輸入的表達較為模糊

沒有說明array的長度，也沒有說明元素和k的具體類型

格外要注意的是，由於在解題過程中需要進行求和操作，我們要謹慎選擇在實現中使用的變數類型。兩數之和的範圍可能遠遠大於單一數字的範圍，所以根據實現語言的不同，要小心避免求和操作造成溢出

小技巧：在面試中，遇到題目中比較模糊的描述，一定記得要和面試官溝通，以便得到更多信息。至少，要向面試官詢問基本的輸入輸出的細節。這樣一來，面試官可以看出你對於問題的思考較為全面和縝密，也是加分項呢

不同公司的面試方法不同，有些會要求候選人寫下完整地實現解法，有些只需要候選人寫出偽代碼就可以了。但是在練習時，我建議大家還是盡量寫下具體的實現，至少也要思考一下實現的細節。

在這個系列裡，我不會給出具體的實現代碼，因為大家掌握的實現語言各不相同。不過，歡迎大家提出實現時遇到的問題，我們可以集思廣益，一起解決～

總結

這道題目很精巧。它不涉及任何著名的，大家耳熟能詳的演算法，但是可以很好地考察候選人對暴力解法進行優化的完整的思考過程，還可以考察候選人對於輸入輸出的要求所進行的思考。

小而強大～也許這就是Google使用這道題目的原因吧～

恭喜各位成功解決了第一道大廠面試真題～可以好好休息一下了～

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！