一个数组，大小跟每个元素的值在编译时已知。设计一个算法用最快速的方式计算两个下标间所有数组元素的和

一个数组，大小和每个元素的值在编译时已知。设计一个算法用最快速的方式计算两个下标间所有数组元素的和
一个数组，大小和每个元素的值在编译时已知。设计一个算法用最快速的方式计算两个下标间所有数组元素的和


小弟想了下

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];
}

[解决办法]

引用:

//初始化代码
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[i] = i == 0 ? 0 : b[i-1] + a[i];  而不是  b[i] = i == 0 ? a[0] : b[i-1] + a[i];
[解决办法]

引用:

//初始化代码
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];
}

还有，您的代码在初始化的时候就使用了for进行累加，而且好像还做了些无用的操作，执行效率也不一定高哟。

我觉得楼主的代码的效率已经算很高了。

查看更多 下一篇