Может ли кто-нибудь указать на ошибку для кода Количество подпоследовательностей, которые удовлетворяют условию данной суммы, которое дает ошибку переполнения стека

Это проблема leetCode. Я решил это, используя следующий метод, но он дает ошибку переполнения стека.

Дан массив целых чисел и целочисленная цель. Возвращает количество непустых подпоследовательностей чисел, так что сумма минимального и максимального элементов в нем меньше или равна целевому. Поскольку ответ может быть слишком большим, верните его по модулю 10 ^ 9 + 7.
Вход: nums = [3,5,6,7], target = 9 Выход: 4 Пояснение: Есть 4 подпоследовательности, удовлетворяющие состояние. [3]: Мин. Значение + макс. Значение ‹= цель (3 + 3‹ = 9) [3,5]: (3 + 5 ‹= 9) [3,5,6]: (3 + 6‹ = 9) [3,6]: (3 + 6 ‹= 9)

enter code here:

import java.lang.Math;
class Solution {
static int maxIndex=0;
static long M=1000000007;
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
maxIndex=nums.length-1;
return numSubseq(nums,target,0);
}

public int numSubseq(int[] nums,int target, int i){
 if(target==0 || nums.length==0 || i==nums.length)
return 0;
int res=0;
if(2*nums[i]<=target){
     res=1;
    if(nums[i]<nums[maxIndex]){
        int j=maxIndex;
        while(j>i){
         if(nums[i]+nums[maxIndex]<=target)
             break;
            j--;
        }
        maxIndex=j;
        if(nums[i]+nums[maxIndex]<=target && i!=maxIndex) 
        {
            int diffIndex=maxIndex-i;
            res+=Math.pow(2,diffIndex)-1;
        }
        
       }
   }
      else{
           return 0;
     }
      return (int)((res+numSubseq(nums,target,i++))%M);
   }
}``

java dsa
person Ashna kohli    schedule 19.11.2020    source источник
comment
Привет, не могли бы вы более подробно объяснить, какую проблему пытается решить код, и показать несколько примеров ввода и вывода? Также можете ли вы объяснить общий подход к решению проблемы, которую вы пытаетесь реализовать в коде? Например, почему в коде используется рекурсия? Также аккуратно отформатируйте код, чтобы было легко увидеть, как выстроились скобки.   -  person Karl Knechtel    schedule 19.11.2020
comment
Я нахожу неподпоследовательности, которые содержат первое число в массиве nums, а остальное количество ненулевых подпоследовательностей получается с использованием рекурсии.   -  person Ashna kohli    schedule 19.11.2020
comment
Чтобы продемонстрировать проблему, предоставьте минимальный воспроизводимый пример. Предлагаю использовать жестко запрограммированный ввод.   -  person Yunnosch    schedule 19.11.2020

Ответы (1)


arrow_upward
1
arrow_downward

  • Думаю, в этой строке может быть проблема:
return (int)((res+numSubseq(nums,target,i++))%M);
  • Однако мы можем решить проблему немного проще, аналогично используя сортировку, а затем два указателя.

Тест с b.java:

import java.util.*;

class Solution {
    private static final int MOD = (int)1e9 + 7;
    public static final int numSubseq(
        final int[] nums,
        final int target
    ) {
        Arrays.sort(nums);
        int[] pows = new int[nums.length];
        pows[0] = 1;

        int subsequences = 0;
        int left = 0;
        int right = nums.length - 1;

        for (int index = 1 ; index < nums.length ; ++index) {
            pows[index] = pows[index - 1] * 2;
            pows[index] %= MOD;
        }

        while (left <= right) {
            if (nums[left] + nums[right] > target) {
                --right;

            } else {
                subsequences += pows[right - left++];
                subsequences %=  MOD;
            }
        }

        return subsequences;
    }
}


class b {
    public static void main(String[] args) {
        System.out.println(new Solution().numSubseq(new int[] {3, 5, 6, 7}, 9));
        System.out.println(new Solution().numSubseq(new int[] {3, 3, 6, 8}, 10));
        System.out.println(new Solution().numSubseq(new int[] {2, 3, 3, 4, 6, 7}, 12));
        System.out.println(new Solution().numSubseq(new int[] {5, 2, 4, 1, 7, 6, 8}, 16));
    }
}

отпечатки

4
6
61
127
person Emma    schedule 19.11.2020