有没有人能指出代码“满足给定求和条件的子序列数”的错误，它给出了堆栈溢出错误
有没有人能指出代码“满足给定求和条件的子序列数”的错误，它给出了堆栈溢出错误
提问于 2020-11-19 13:48:28
这就是leetCode问题。我用下面的方法解决了这个问题，但是它给出了堆栈溢出错误。
给定一个整数数组和一个整数目标。返回nums的非空子序列的个数，使其上的最小和最大元素之和小于或等于目标。因为答案可能太大，所以返回模10^9 + 7。
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);
}
}``回答 1
Stack Overflow用户
发布于 2020-11-19 22:21:12
- 我猜这一行会有一个问题：
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64906067
复制相关文章
相似问题
腾讯云开发者
