Рекурсия: Определите, есть ли два элемента в массиве A, сумма которых равна k

Question

Я видел, что этот вопрос задал много. Я получаю, как это работает: мы проверяем сумму первого и последнего. Если эта сумма больше k, то последняя - или если ее меньше k, то сначала ++. Это происходит рекурсивно до тех пор, пока не будет найден первый или последний или сумма 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); 
} 

Answer 1

Две проблемы:

1. j--, будет использовать J, а затем -. он должен быть j - 1 или --j. Такая же история с i ++.

2. Параметр 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); 
} 

Answer 2

О (п) Алгоритм:

1. Вставка элементов массива в хэш-таблицу или HashMap
2. итерации массива и увидеть k - currentElement присутствует в хеш-структуре данных