+-
这是我编写的功能。
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)
的肯定会发生回溯。