僞代碼用於陣列搜索

Question

問題：

「寫入該給定的陣列A和整數數值K它返回值真，如果有所述的那筆兩個不同的整數爲k的算法，並將其返回否則就會失敗。「

我的僞代碼：

輸入：用K值

輸出大小爲n的數組A：如果在總和爲k兩個不同的整數，否則爲false

Algorithm ArraySum(A, n, k) 
for (i=0, i<n, i++) 
    for (j=i+1, j<n, j++) 
     if (A[i]+A[j]=k) 
      return true 
return false 

。我寫這個算法正確嗎？我沒有看到任何錯誤嗎？

Answer 1

如果兩個不同的整數意味着A[i], A[j]其中i != j而不是A[i] != A[j]，你的僞代碼是正確的。

Answer 2

它看起來像knapsack problem的一些情況。

對於你的情況（只有兩個數字），可能會更好地排序你的數組以減少比較次數（A [i] + A [j] = k）。

例如：

you have sorted array [1 3 5 8 10 12 14 20 50 60 100] 
sum of two numbers must be equal to 30 

然後，你可以寫

while(a[i] <= 30) { 
    while(a[i] + a[j] <= 30) { 
    // ... 
    i++; 
    j++; 
    } 
} 

Answer 3

有兩個解決方案在我腦海裏關於這個問題

首個解決方案

詞根記憶空哈希
2.Mark哈希

for each i (Array A){ 
     hash[i] = 1; 
    } 

所有數陣列3.運行一個O(n)迴路

for each i (Array A) 
    if( hash[ k - i ]) 
     print "solution i and k-i" 

這會給你O(n)複雜

第二種解決

1.Sort陣列
2.Run的O(n)循環遍歷數組排序

for each i (Array A) 
    binary_search(Array, k - i); [log n operation] 

這會給你O(n logn)複雜。