有沒(méi)有比強(qiáng)力搜索更有效的算法來(lái)找到三個(gè)整數(shù)？
是的; 我們可以在O（n 2）時(shí)間內(nèi)解決這個(gè)問(wèn)題！首先，考慮一下你的問(wèn)題P可以用一種略微不同的方式來(lái)表達(dá)，從而消除了對(duì)“目標(biāo)值”的需求：
原來(lái)的問(wèn)題P：給定一個(gè)陣列A的n整數(shù)和目標(biāo)值S，就存在著從一個(gè)3元組A求和以S？
改性問(wèn)題P'：給定一個(gè)陣列A的n整數(shù)，不存在從3元組A求和為零？
請(qǐng)注意，您可以從這個(gè)版本的問(wèn)題，去P'從P通過(guò)從每個(gè)元素減去你的S / 3 A，但現(xiàn)在你不需要目標(biāo)值了。
顯然，如果我們只是測(cè)試所有可能的3元組，我們就可以解決O（n 3）中的問(wèn)題 - 這就是蠻力基線。有可能做得更好嗎？如果我們以更聰明的方式選擇元組怎么辦？
首先，我們花費(fèi)一些時(shí)間對(duì)數(shù)組進(jìn)行排序，這使我們的初始懲罰為O（n log n）。現(xiàn)在我們執(zhí)行這個(gè)算法：
for (i in 1..n-2) {
j = i+1 // Start right after i.
k = n // Start at the end of the array.
while (k >= j) {
// We got a match! All done.
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
// We didn't match. Let's try to get a little closer:
// If the sum was too big, decrement k.
// If the sum was too small, increment j.
(A[i] + A[j] + A[k] > 0) ? k-- : j++
}
// When the while-loop finishes, j and k have passed each other and there's
// no more useful combinations that we can try with this i.}該算法的工作原理是將三分，i，j，并k在不同的點(diǎn)在數(shù)組中。i從一開(kāi)始就開(kāi)始慢慢地運(yùn)行到最后。k指向最后一個(gè)元素。j指向i已經(jīng)開(kāi)始的地方。我們迭代地嘗試在各自的索引處對(duì)元素求和，并且每次發(fā)生以下情況之一：
對(duì)于每一個(gè)i，指針j和k將逐漸變得彼此靠近。最終它們會(huì)相互傳遞，此時(shí)我們不需要為此嘗試任何其他因素i，因?yàn)槲覀冎皇且圆煌捻樞驅(qū)ο嗤脑剡M(jìn)行求和。在那之后，我們嘗試下一個(gè)i并重復(fù)。
最終，我們將耗盡有用的可能性，或者我們將找到解決方案。你可以看到這是O（n 2），因?yàn)槲覀儓?zhí)行外循環(huán)O（n）次，我們執(zhí)行內(nèi)循環(huán)O（n）次。如果您真的很喜歡，可以通過(guò)將每個(gè)整數(shù)表示為位向量并執(zhí)行快速傅立葉變換來(lái)實(shí)現(xiàn)這種子二次方，但這超出了本答案的范圍。
注意：因?yàn)檫@是一個(gè)面試問(wèn)題，我在這里做了一點(diǎn)作弊：這個(gè)算法允許多次選擇相同的元素。也就是說(shuō)，（-1，-1,2）將是一個(gè)有效的解決方案，因?yàn)椋?,0,0）。它也只能找到確切的答案，而不是最接近的答案，正如標(biāo)題所提到的那樣。作為對(duì)讀者的練習(xí)，我將讓你弄清楚如何使它只使用不同的元素（但這是一個(gè)非常簡(jiǎn)單的變化）和確切的答案（這也是一個(gè)簡(jiǎn)單的變化）。
