遞歸：確定數組A中是否有兩個元素總和爲k

我見過這個問題問了很多。我知道它是如何工作的：我們檢查第一個和最後一個的總和。如果這個總和大於k，那麼最後 - 或者如果它小於k，則第一個++。這是遞歸地進行，直到first == last或找到總和k。 **注意數組中的值總是按升序排序。遞歸：確定數組A中是否有兩個元素總和爲k

我試過使用遞歸，但每當我運行它時，它總是返回「false」。我已經嘗試過所有大小的數組，所有的測試用例都返回false。例如數組[1 2 3 4 5 6]，大小n = 6和k = 7在應該爲真時返回false。我似乎無法找到該錯誤。任何人都可以請我指出我在犯我的錯誤嗎？如果我沒有弄錯，它會在O（n）時間運行嗎？

public static boolean sum(int[] A, int n, int k) //where k is the sum needed and n the size of the array 
{ 
    if (k <= A[0] || k >= A[n]*2) 
    { 
      return false; 
    } 
    int i = 0; 
    int j = n-1; 
    return sum_Recursion(A, n, k, i, j); 
} 


private static boolean sum_Recursion(int[] A, int n, int k, int i, int j) 
{ 
    if(i == j) 
    { 
     return false; 
    } else if((A[i] + A[j]) == k)  
    { 
     return true; 
    } else if ((A[i] + A[j]) > k) 
    { 
     return sum_Recursion(A, n, k, i, j--); 
    } 
     return sum_Recursion(A, n, k, i++, j); 
}

來源

2016-02-08 RYS221

這應該是O（n），顯示問題的最小輸入是多少？當您嘗試在調試器中調試代碼時，您看到了什麼？注意：'sum_recursion'不使用'n'。爲什麼'j = n - 1'？如果需要最後一個值怎麼辦？ –

@PeterLawrey對於任何輸入，即我給它一個數組，然後用k值對它進行測試，該值是該數組中兩個整數以及其他k的總和......在任何情況下，它都返回false。這從來都不是真的。 n是數組的大小（它是作爲參數給出的，所以我對最後一個索引做了j = n-1） – RYS221

如果'n'是數組的大小'A [n]'總是會拋出異常。我建議你用'A.length'作爲數組的大小。 –

兩個問題：

的j--，將首先使用j時， - 。它應該是j - 1或 - j。與i ++同樣的故事。
n參數似乎沒用。什麼時候使用它，索引超出範圍。

修正版本與正確的結果：

public static void main(String[] args) { 
    int[] a = {1, 2, 3, 4, 5, 6}; 
    System.out.println(sum(a, 6, 7)); // ==> true 
} 

public static boolean sum(int[] A, int n, int k) //where k is the sum needed and n the size of the array 
{ 
    if (k <= A[0] || k >= A[n - 1] * 2) { 
     return false; 
    } 
    int i = 0; 
    int j = n - 1; 
    return sum_Recursion(A, n, k, i, j); 
} 


private static boolean sum_Recursion(int[] A, int n, int k, int i, int j) { 
    if (i == j) { 
     return false; 
    } else if ((A[i] + A[j]) == k) { 
     return true; 
    } else if ((A[i] + A[j]) > k) { 
     return sum_Recursion(A, n, k, i, j - 1); 
    } 
    return sum_Recursion(A, n, k, i + 1, j); 
}

來源

2016-02-08 02:13:49 xfx

注意：您的版本也會找到-1 + 2 = 1，OP的版本假定沒有值是負值。 +1 –

謝謝。哦，這是有道理的，我應該意識到這一點！：|我沒有關於n參數的選擇，我們給了方法頭，並且必須使用給定的參數完成代碼。我改變了關於i和j的代碼，但不幸的是它仍然返回false。 :( – RYS221

@ user156177已更新答案。將A [n] * 2更改爲A [n-1] * 2. – xfx

的O（n）的算法：

插入數組元素爲哈希表或散列映射
迭代陣列上方和看k - currentElement存在於散列數據結構中

來源

2016-02-08 03:22:12

遞歸：確定數組A中是否有兩個元素總和爲k

回答

相關問題