Ошибка переполнения стека в сумме подмассива минимального размера

Question

Мой код не работает для s = 120331635 и очень длинного массива. Пожалуйста, найдите массив здесь

<a href="http://www.filedropper.com/arraytnt" rel="nofollow noreferrer">http://www.filedropper.com/arraytnt</a> 

. Я получаю сообщение об ошибке Исключение в потоке "main" java.lang.StackOverflowError на Solution.fsub (Solution.java:17) , которое появляется несколько раз.

Q. Для массива из n натуральных чисел и натурального s найти минимальную длину непрерывного подмассива, сумма которого ≥ s. Если его нет, верните 0.

Пример:

Ввод: s = 7, nums = [2,3,1,2,4,3] Выход: 2 Пояснение: подрешетка [4,3] имеет минимальную длину при ограничении задачи

Решение класса {

public int minSubArrayLen(int s, int[] nums) {
    if(nums.length==0) return 0;
    return fsub(s,nums,0,1);
}

public int fsub(int s, int[] A, int i, int f){
    int n=A.length;

    if(f>n) return fsub(s,A,0,f-i+1);
    int sum = 0; for(int j = i;j<f;j++) {sum += A[j];}

    if(sum>=s) return(f-i);      // if found
    else if(f-i == n) return 0;  // if nothing found

    return fsub(s,A,i+1,f+1);

}

}

Answer 1

Используя рекурсию, при каждом вызове метода он использует стек методов, который будет занимать память. Таким образом, если его временная сложность составляет O (2 ^ n), где n - размер массива, то его пространственная сложность будет O (2 ^ n) для вызовов этого множества методов. Таким образом, пространство 2 ^ n пересекает заданные пределы памяти.