+-
这是我编写的功能。
public static boolean existsSum(int[] arr, int n, int sum){
if(sum==0)
return true;
if(n<=0)
return false;
if(arr[n-1] == sum)
return true;
if(sum<0)
return false;
if(sum<arr[n-1])
return existsSum(arr, n-1,sum);
return existsSum(arr, n-1, sum-arr[n-1]) || existsSum(arr, n-1,sum) ;
}
这很好用。但是，只要我更改了最后一行代码，就这样
public static boolean existsSum(int[] arr, int n, int sum){
if(sum==0)
return true;
if(n<=0)
return false;
if(arr[n-1] == sum)
return true;
if(sum<0)
return false;
if(sum<arr[n-1])
return existsSum(arr, n-1,sum);
return existsSum(arr, n-1,sum) || existsSum(arr, n-1, sum-arr[n-1]) ;
}
超过时间限制。我不明白更改顺序对执行时间有什么影响。请帮助。
1
投票
投票
注意||短路，即a || b，如果a为真，则不评估b。
||的两个操作数之间的区别是existsSum(arr, n-1, sum-arr[n-1])将当前项“加”到总和的项目列表中，而existsSum(arr, n-1, sum)则不。
在第一个代码段中，如果existsSum(arr, n-1, sum-arr[n-1])为true，则甚至不会调用existsSum(arr, n-1, sum)。想象一下，我使用数组[1,2,3]和总和6来调用它。第一个操作数将在每个递归调用中返回true，并且不需要评估第二个操作数。
[类似地，在第二个代码片段中，existsSum(arr, n-1, sum)首先运行，如果为true，则不调用existsSum(arr, n-1, sum-arr[n-1])。但是，existsSum(arr, n-1, sum)不能返回true 。我的意思是，要使调用existsSum(arr, n-1, sum)返回true，值true必须来自对existsSum(arr, n-1, sum-arr[n-1])的递归调用。您可以通过分析不同的分支来验证这一点。这意味着[existsSum(arr, n-1, sum)的肯定会发生回溯。
