一个数组，大小和每个元素的值在编译时已知。设计一个算法用最快速的方式计算两个下标间所有数组元素的和
小弟想了下int beginIndex;
int endIndex;
for(int i=beginIndex;i<=endIndex;i++){
sum+=a[i];
}时间复杂度是O(length)最坏的情况是0 - array.length
不会就这么简单吧？求各位给看看，小弟感激不敬
小弟想了下int beginIndex;
int endIndex;
for(int i=beginIndex;i<=endIndex;i++){
sum+=a[i];
}时间复杂度是O(length)最坏的情况是0 - array.length
不会就这么简单吧？求各位给看看，小弟感激不敬
int [] b = new int[a.length];
for (int i=0; i<a.length; i++)
b[i] = i == 0 ? 0 : b[i-1] + a[i];public int getSum(beginIndex, endIndex) {
return b[endIndex] - beginIndex == 0 ? 0 : b[beginIndex - 1];
}
我把你的代码改了下作了下调试你看是这样的不？
/* 程序初始化时，重新定义一个数组，数组的元素是目标数组中每个元素到目标数组开始位置的所有元素的和
例如b[2]=a[0]+a[1]+a[2]
*/
int[] b = new int[a.length];
for (int i = 0; i < a.length; i++)
b[i] = i == 0 ? a[0] : b[i - 1] + a[i];
/**
* 题目二：一个数组，大小和每个元素的值在编译时已知
* 设计一个算法用最快速的方式计算两个下标间所有数组元素的和。
* @param a 被计算的数组
* @param beginIndex 数组被计算和的开始位置下标
* @param endIndex 数组被计算和的结束位置下标
* @return 下标间所有数组元素的和
* @throws Exception 下标值不满足要求时抛出异常
*/
public int getSum(int beginIndex, int endIndex) throws Exception {
if (endIndex > a.length -1) {
throw new IndexOutOfBoundsException("结束下标超过数组长度");
}
if (beginIndex < 0) {
throw new IndexOutOfBoundsException("开始下标小于0");
}
if ((endIndex - beginIndex < 0)) {
throw new Exception("被计算的结束下标需要比开始下标大");
}
return endIndex - beginIndex == 0 ? 0 : b[endIndex]- b[beginIndex]+ a[beginIndex];
}