搜索值

Question

的總和的陣列的I具有在其中包含的值低於1

線的文本文件，生成值的系統：總計值可能

行2：未在元件的陣列

3號線（如果需要額外的線路）：數字本身

我現在在想辦法，我可以減去總價值從數組中的第一個整數開始，然後在數組中搜索餘數，然後執行相同操作直到找到該對。

另一種方法是在排列和組合基礎上添加數組中的兩個整數並找到該對。

根據我的分析，第一種解決方案更好，因爲它減少了迭代次數。這裏我的分析是否正確，還有其他更好的方法嗎？

編輯： 我將在這裏得到樣品，使之更加清楚 第1行：200 行2 = 10 線路3：10 20 80 78 19 25 198 120 12 65

現在有效這裏是80,120，因爲它總計爲200（在第一行中表示爲輸入文件中可能的總值）並且它們在數組中的位置將是3,8。所以找到這對我列出了我的方法，第一個元素，我用Total值減去它，然後通過基本搜索算法搜索另一個元素。

使用這裏的例子，我先取10並用200減去190得出190，然後我搜索190，如果找到了，那麼找到這對，否則繼續相同的過程。

Answer 1

如果你想找到一對（2）和第三號，一般你會碰到這樣的數字：

for(i=0;i<N;i++) 
    for(j=i+1;j<N;j++) 
     if(numbers[i]+numbers[j]==result) 
     The answer is <i,j> 
     end 

這是O（n^2）。但是，可以做得更好。

如果號碼的列表進行排序（這需要爲O（n log n）的時間），那麼你可以嘗試：

for(i=0;i<N;i++) 
    binary_search 'numbers[i+1:N]' for result-numbers[i] 
    if search succeeds: 
     The answer is <i, search_result_index> 
     end 

也就是說，你可以通過每個數字步驟，然後做一個二進制搜索上其同伴號碼的剩餘列表。這需要O（n log n）時間。您可能需要在自己上面實現search函數，因爲內置函數可能只是在O（n）時間內走到列表中，導致O（n^2）結果。

對於這兩種方法，您都需要檢查當前數字是否與您的結果相同的特殊情況。

這兩種算法都不會使用比陣列本身佔用更多的空間。

對於編碼風格的道歉，我對Java並不熟悉，這裏的想法很重要。

Answer 2

你的問題是模糊的，但如果你正在尋找相加一定數量陣列中一對，也可以在O(n)平均使用哈希表來完成。

迭代陣列，併爲每個元素：
（1）檢查它是否在表中。如果是這樣 - 停止並返回就有這樣一對。
（2）否則：將num-element插入散列表。

如果你的迭代沒有找到匹配就終止 - 沒有這樣的對。

僞代碼：

checkIfPairExists(arr,num): 
    set <- new empty hash set 
    for each element in arr: 
     if set.contains(element): 
      return true 
     else: 
      set.add(num-element) 
    return false 

的一般問題「是有求和到一定數量的子集」是NP-Hard，並且是被稱爲subset-sum problem，所以沒有已知的多項式的解決方案它。