分治数组迭代求和

Question

是否可以使用分治法求数组的总和？我已经试过了，但总是漏掉一些数字，或者我计算了两次数字。

int[] arr = new int[]{1,2,3,4,5};

    public int sum(int[] arr) {
        int begin = 0;
        int end = array.length - 1;
        int counter = 0;

        while (begin <= end) {
            int mid = (begin + end) / 2;
            counter += arr[end] + arr[mid];
            end = mid - 1;
        }
        return counter;
    }

Answer 1

当然，数组和的分而治之计算是可能的。但是我看不到它的用例？你仍在计算至少相同数量的总和，如果 array 的总和大于 Integer.MAX_VALUE，你仍然运行有问题，...

也没有像 Codor 在他的相关问题中显示的性能优势。

从 Java 8 开始，您可以使用流在 1 行中计算总和。

int sum = Arrays.stream(array).sum();

上述代码的主要缺陷是您只对索引 mid(2) 和 end(4) 求和。之后跳到下括号（索引 mid = 0 和 end = 2）。所以你缺少索引 3。这个问题会随着数组的增加而变得更加普遍，因为在 while 的第一次迭代之后你跳过了更多的索引。

快速 Google 搜索提出了 this nice-looking talk 使用称为递归的机制的一般分而治之原则。也许它可以指导您找到可行的解决方案。

分治数组迭代求和

Divide and conquer sum of array iterative

java

arrays

sum

divide-and-conquer