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

常聽人說(shuō)，算法很難。這話沒錯(cuò)。算法本身是是一個(gè)艱深的方向。但是算法題卻有據(jù)可循。通過(guò)有針對(duì)性的學(xué)習(xí)和練習(xí)，我們完全可以掌握解題的基本方法和技巧，見題拆題，掃清通往offer之路上的障礙。

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

接下來(lái)，就讓我們來(lái)看第一題：

題目

[來(lái)自Google]

Given a list of numbers and a number k, return whether any two numbers from the list add up to k

給定一組數(shù)字，以及一個(gè)數(shù)字k，確定這組數(shù)字中，是否存在任意兩個(gè)數(shù)字，其相加之和等于k。

解析

初次見到一個(gè)問(wèn)題，如果暫時(shí)沒有什么特別清晰的思路或靈感，不妨安下心來(lái)，首先想一想這道題目的暴力解法。

簡(jiǎn)單粗暴的暴力解法不考慮效率和美觀，只考慮正確性，所以往往效率較低。但是，通過(guò)觀察暴力解法中冗余或者重復(fù)的部分，我們就可以找到進(jìn)一步優(yōu)化的切入點(diǎn)，想出更有效率的算法。

小技巧： 在面試中，如果暫時(shí)頭腦空白，想不到漂亮的解法，不妨坦率地用簡(jiǎn)潔的話語(yǔ)先描述一下暴力解法，在這個(gè)過(guò)程中發(fā)現(xiàn)思路，找到優(yōu)化解法。這個(gè)過(guò)程，也有助于面試官考察你的整體解題思路，還可能給你加分喲

暴力解法

這道題的暴力解法很簡(jiǎn)單。 只要將數(shù)組中所有數(shù)字對(duì)求和，然后和給定的數(shù)字k相比較，就知道是否有和k相等的值了。 假設(shè)數(shù)組中有n個(gè)數(shù)字，將暴力解法寫成偽代碼pseudo code的話，就是這個(gè)樣子：

function sumEqualsToK(array, k): for i=1 to n-1for j=n+1 to nif array[i] + array[j] == kreturn true return false

暴力解法使用了兩個(gè)嵌套在一起的循環(huán)，顯而易見，它的時(shí)間復(fù)雜度是O(n^2)。為了降低時(shí)間復(fù)雜度，我們來(lái)分析一下暴力解法中冗余或者重復(fù)的部分。

暴力解法試圖對(duì)數(shù)組中所有 數(shù)字對(duì)進(jìn)行求和操作。 這部分操作是否存在冗余的部分呢？ 我們能不能減少需要查看的數(shù)字對(duì)的數(shù)量呢？ 想要對(duì)這一點(diǎn)進(jìn)行優(yōu)化，我們就要利用題目中的另一個(gè)線索，也就是數(shù)字k了。

其實(shí)這道題目就是在給元素“配對(duì)兒”。 對(duì)于數(shù)組中的任一數(shù)字array[i]，如果希望它和它的“另一半”相加之和等于k，那就意味著它的“另一半”的值必須是k-array[i]。 也就是說(shuō)，只要數(shù)組中也存在一個(gè)等于k-array[i]的元素，就可以滿足相加等于k這個(gè)條件了：

例子： k = 10 array = [ 4, 2, 5, 6, 8 ]那么我們尋找的“另一半”們就是：[ 10-4, 10-2, 10-5, 10-6, 10-8 ] 也就是 [6, 8, 5, 4, 2]這樣一來(lái)，我們的問(wèn)題就轉(zhuǎn)換成： 給定數(shù)組 array = [ 4, 2, 5, 6, 8 ]，以及數(shù)組 target = [ 6, 8, 5, 4, 2 ]， array[i]和target[i]是不是同時(shí)存在于array中在這個(gè)例子中，大家要格外關(guān)注5這個(gè)元素 5正好是k值的一半，所以array和target都包含了5 只有在原數(shù)組中包含了兩個(gè)5，才能相加等于10

好了，現(xiàn)在我們已經(jīng)有了進(jìn)一步優(yōu)化暴力解法的思路了。 在揭曉優(yōu)化解法的偽代碼之前，請(qǐng)你先開動(dòng)腦筋，試著自己把代碼寫出來(lái)吧

思考～思考～

優(yōu)化解法

時(shí)間到～下面就是優(yōu)化算法的偽代碼了：

function sumEqualsToK(array, k): for i=1 to nif map contains array[i]return trueelseput k-array[i] into map return false

在優(yōu)化算法中，我們使用了一個(gè)map來(lái)記錄我們想要尋找的“另一半”的元素，也就是之前例子里面提到的target

接下來(lái)，我們只需要遍歷array一次。 如果array[i]已經(jīng)和map中的元素相符，就說(shuō)明array[i]和我們之前遍歷到的某一個(gè)元素恰好是相加為k的“一對(duì)兒”，算法直接返回true。 如果不相符，那么我們就把k-array[i]放進(jìn)map中去，期待接下來(lái)遍歷到的元素能夠和k-array[i]相符。

這個(gè)優(yōu)化算法只需要遍歷array一次，所以它的時(shí)間復(fù)雜度只有O(n)。而我們最多也只會(huì)將array中所有元素的“另一半”放進(jìn)map中去，所以算法的空間復(fù)雜度也是O(n)

實(shí)現(xiàn)

想出解法只是第一步，為了正確地實(shí)現(xiàn)解法，我們還需要考慮實(shí)現(xiàn)中的細(xì)節(jié)。 讓我們想一想這個(gè)問(wèn)題的輸入和輸出：

輸出

這個(gè)問(wèn)題的輸出很簡(jiǎn)單，就是一個(gè)boolean值，true/false

輸入

題目中對(duì)于輸入的表達(dá)較為模糊 沒有說(shuō)明array的長(zhǎng)度，也沒有說(shuō)明元素和k的具體類型 格外要注意的是，由于在解題過(guò)程中需要進(jìn)行求和操作，我們要謹(jǐn)慎選擇在實(shí)現(xiàn)中使用的變量類型。兩數(shù)之和的范圍可能遠(yuǎn)遠(yuǎn)大于單一數(shù)字的范圍，所以根據(jù)實(shí)現(xiàn)語(yǔ)言的不同，要小心避免求和操作造成溢出

小技巧：在面試中，遇到題目中比較模糊的描述，一定記得要和面試官溝通，以便得到更多信息。至少，要向面試官詢問(wèn)基本的輸入輸出的細(xì)節(jié)。這樣一來(lái)，面試官可以看出你對(duì)于問(wèn)題的思考較為全面和縝密，也是加分項(xiàng)呢

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

在這個(gè)系列里，我不會(huì)給出具體的實(shí)現(xiàn)代碼，因?yàn)榇蠹艺莆盏膶?shí)現(xiàn)語(yǔ)言各不相同。不過(guò)，歡迎大家提出實(shí)現(xiàn)時(shí)遇到的問(wèn)題，我們可以集思廣益，一起解決～

總結(jié)

這道題目很精巧。它不涉及任何著名的，大家耳熟能詳?shù)乃惴?#xff0c;但是可以很好地考察候選人對(duì)暴力解法進(jìn)行優(yōu)化的完整的思考過(guò)程，還可以考察候選人對(duì)于輸入輸出的要求所進(jìn)行的思考。 小而強(qiáng)大～也許這就是Google使用這道題目的原因吧～

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

[轉(zhuǎn)載請(qǐng)注明]

---

歡迎關(guān)注課程：

一站式學(xué)習(xí)Java網(wǎng)絡(luò)編程_全面理解BIO/NIO/AIO-慕課網(wǎng)實(shí)戰(zhàn)?coding.imooc.com全面掌握MongoDB 4.0-完成從小白到達(dá)人的蛻變-慕課網(wǎng)實(shí)戰(zhàn)?coding.imooc.comMongoDB 4.0新特性?www.imooc.com

總結(jié)

以上是生活随笔為你收集整理的给定数组 求和等于固定值 算法_[见题拆题] 大厂面试算法真题解析 - 第一期开张...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。