如何檢查3個數字的數組，添加到JAVA中的特定值？

好吧，夥計們，我一直在這個問題上停留了一段時間，並且一直無法通過它。這是針對Java的。在這一點上，我很感激任何幫助。以下是詳細信息：請注意，我們必須在O（n）運行時間內執行此操作。我們給出了一系列數字，並且必須通過它來確定是否有任何3個數字總和爲特定數字。但是，我們可以重複使用陣列中的任何數字3次，因爲我們總共需要3個數字。我們還必須輸出哪3個數字給出了總和。返回真或假。如何檢查3個數字的數組，添加到JAVA中的特定值？

下面是我的本錢：

。你們有什麼建議？

來源

2014-09-20 Vimzy

您正在使用'Arrays.sort' - 這排除了'O（n）'算法，因爲'sort'本身就是'> O（n）'。 – OldCurmudgeon 2014-09-20 20:58:14

如果它是2個數字，它可以通過使用HashSet或具有O（1）訪問和減法的類似結構在O（n）中完成，但是它是3，因此您可能獲得的最好結果是O（n^2）。如果是4個數字，最好的情況複雜度是O（n^3）等等......當然這是假設n個數字沒有限制，而且它們是任意的。 – Shashank 2014-09-20 21:19:25

您可以在for循環中的for循環中創建一個for循環。這是爲了學校，所以我不會給你代碼，但我會給你僞代碼。

編輯：錯過了O（n）部分，對不起。這種方式應該工作。

public static void main(String[] args) 
{ 
int[] test = {1,8,2,3,11,4}; 
System.out.println(threeSumTo(test, 6)); 
} 

//check if 3 numbs in an array add up to int x 
public static boolean threeSumTo(int[] array, int x) 
{ 
//loop through the array 
for (int i = 0; i < array.length; i++) { 
    boolean result = twoSumTo(array, x - array[i], i); 
    if (result) { 
     return result; 
    } 
} 
return false; 
} 

private static boolean twoSumTo(int[] array, int x, int low) { 
int high = array.length - 1; 
while (low < high) { 
    if (array[low] + array[high] == x) { 
     return true; 
    } 
    if (array[low] + array[high] > x) { 
     high--; 
    } else { 
     low++; 
    } 
} 
return false; 
} 
}

來源

2014-09-20 20:47:15 LeChosenOne

但這有一個O（n^3）運行時間，我需要O（n）甚至O（n^2log n）的東西。 – Vimzy 2014-09-20 20:49:19

對不起，我編輯了它。現在，第一個布爾值通過每個數字循環，第二個循環通過不同的數字組合。那是你在找什麼？ – LeChosenOne 2014-09-20 20:58:03

它確實工作，但它需要很長時間，所以我仍然不認爲它是O（n）不幸的是:( – Vimzy 2014-09-20 21:08:59

這似乎是3SUM problem的變體，應遵守相同的限制。

計算小於O（n^2）的3SUM問題仍然是一個沒有解決的問題。

您的老師是否提出了一個詭計問題或者是某種競爭？

來源

2014-09-20 21:13:11 dfherr

他一定是一直在搞亂，因爲我現在就像在摸索着我...... – Vimzy 2014-09-20 21:13:59

好吧，AceOfBlades的建議至少在O（n^2）附近計算。Perhabs他希望有人能解決這個未解決的問題，好主意：D他可能不想讓他的學生在stackoverflow上問，雖然^^ – dfherr 2014-09-20 21:18:53

它只是到了我太好奇的地步了！我無法理解這可能是O（n）和我猜猜它不能...大聲笑 – Vimzy 2014-09-20 21:20:32

這被稱爲3求和問題，直到現在，解決O（N）中的這個問題是不可能的。你能做的最好的是O（N^2）。

檢查this article out。

來源

2014-09-20 21:15:31 Adelin

如何檢查3個數字的數組，添加到JAVA中的特定值？

回答

相關問題