最有效的方法来总结一个整数数组

Question

我试图找到一个子O(n)方法来计算整数数组的总和~~~(而不是迭代0 - n,我正在做n/2)~~~ 我仍然在O(n)中做它.

public static int sum(int[] s) {
    int length = s.length - 1;
    int half = length/2;
    int sum = 0;
    for(int i = 0; i <= half; i++) {
        System.out.println(i + " " + s[i] + " + " + s[length - i]);
        sum += s[i] + s[length - i];
    }
    return sum;
}

我的算法适用于偶数个整数,但是,当有奇数个整数时,它会将中间索引加两次:

测试:

    int[] arr = {1, 2, 3, 4, 5};
    System.out.println(sum(arr));

输出:

0 1 + 5
1 2 + 4
2 3 + 3
Sum: 18

我的问题是 - 总结奇数个数的中间指数的最佳方法是什么？

Answer 1

这仍然是O(n),即使你在一天结束时从0到n/2,你至少要触摸一次阵列的每个元素.总结一个整数数组,你可以做的最少的是O(n)因为你必须触摸数组中的每个元素一次以将它包含在总和中.