查找數組中的三個元素，其總和最接近給定數字給定一個整數數組，A 1，A 2，...，A n，包括負數和正數，以及另一個整數S.現在我們需要在數組中找到三個不同的整數，其總和最接近給定的整數S如果存在多個解決方案，則其中任何一個都可以。您可以假設所有整數都在int32_t范圍內，并且計算總和時不會發生算術溢出。S沒什么特別的，只是隨機挑選的數字。有沒有比強力搜索更有效的算法來找到三個整數？
3 回答
胡子哥哥
TA貢獻1825條經驗 獲得超6個贊
有沒有比強力搜索更有效的算法來找到三個整數？
是的; 我們可以在O（n 2）時間內解決這個問題！首先，考慮一下你的問題P可以用一種略微不同的方式來表達，從而消除了對“目標值”的需求：
原來的問題
P：給定一個陣列A的n整數和目標值S，就存在著從一個3元組A求和以S？改性問題
P'：給定一個陣列A的n整數，不存在從3元組A求和為零？
請注意，您可以從這個版本的問題，去P'從P通過從每個元素減去你的S / 3 A，但現在你不需要目標值了。
顯然，如果我們只是測試所有可能的3元組，我們就可以解決O（n 3）中的問題 - 這就是蠻力基線。有可能做得更好嗎？如果我們以更聰明的方式選擇元組怎么辦？
首先，我們花費一些時間對數組進行排序，這使我們的初始懲罰為O（n log n）?，F在我們執行這個算法：
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在不同的點在數組中。i從一開始就開始慢慢地運行到最后。k指向最后一個元素。j指向i已經開始的地方。我們迭代地嘗試在各自的索引處對元素求和，并且每次發生以下情況之一：
總和是完全正確的！我們找到了答案。
總和太小了。移動
j更接近最終選擇未來最大數量。總和太大了。移動
k接近開始選擇下一個最小的數。
對于每一個i，指針j和k將逐漸變得彼此靠近。最終它們會相互傳遞，此時我們不需要為此嘗試任何其他因素i，因為我們只是以不同的順序對相同的元素進行求和。在那之后，我們嘗試下一個i并重復。
最終，我們將耗盡有用的可能性，或者我們將找到解決方案。你可以看到這是O（n 2），因為我們執行外循環O（n）次，我們執行內循環O（n）次。如果您真的很喜歡，可以通過將每個整數表示為位向量并執行快速傅立葉變換來實現這種子二次方，但這超出了本答案的范圍。
注意：因為這是一個面試問題，我在這里做了一點作弊：這個算法允許多次選擇相同的元素。也就是說，（-1，-1,2）將是一個有效的解決方案，因為（0,0,0）。它也只能找到確切的答案，而不是最接近的答案，正如標題所提到的那樣。作為對讀者的練習，我將讓你弄清楚如何使它只使用不同的元素（但這是一個非常簡單的變化）和確切的答案（這也是一個簡單的變化）。
有只小跳蛙
TA貢獻1824條經驗 獲得超8個贊
當然這是一個更好的解決方案，因為它更容易閱讀，因此不容易出錯。唯一的問題是，我們需要添加幾行代碼以避免多個選擇一個元素。
另一個O（n ^ 2）解決方案（使用hashset）。
// K is the sum that we are looking forfor i 1..n int s1 = K - A[i] for j 1..i int s2 = s1 - A[j] if (set.contains(s2)) print the numbers set.add(A[i])
蝴蝶刀刀
TA貢獻1801條經驗 獲得超8個贊
這樣的事情怎么樣，這是O（n ^ 2）
for(each ele in the sorted array){
ele = arr[i] - YOUR_NUMBER;
let front be the pointer to the front of the array;
let rear be the pointer to the rear element of the array.;
// till front is not greater than rear.
while(front <= rear)
{
if(*front + *rear == ele)
{
print "Found triplet "<<*front<<","<<*rear<<","<<ele<<endl;
break;
}
else
{
// sum is > ele, so we need to decrease the sum by decrementing rear pointer.
if((*front + *rear) > ele)
decrement rear pointer.
// sum is < ele, so we need to increase the sum by incrementing the front pointer.
else
increment front pointer.
}
}這會發現3個元素的總和是否與您的數字完全相等。如果你想要最接近，你可以修改它以記住最小的三角形（當前三元組的數量之間的差異），最后打印對應于最小三角形的三元組。
添加回答
舉報
0/150
提交
取消