迭代式分治法求解数组总和的可行性及代码问题排查

核心结论 #

完全可以使用分治法计算数组的总和，你的问题出在代码实现逻辑不符合分治的规则，而非分治法本身不适用。

现有代码错误排查 #

• 变量名错误：方法入参定义为arr，但计算end边界时调用了未定义的变量array，代码无法正常编译运行
• 逻辑不符合分治要求：你编写的循环逻辑没有遵循分治「拆分独立子问题、子问题求解后合并结果」的核心思路，每次仅累加mid和end位置的元素，会遗漏大量未被遍历的数组元素。以你的测试用例[1,2,3,4,5]为例，代码会直接漏掉索引为3的数值4，最终得到错误结果11，而非正确总和15。

正确分治实现方案 #

实现思路 #

1. 递归终止条件：当子数组左边界大于右边界时返回0；当左右边界相等时直接返回当前位置的元素值
2. 拆分规则：取当前子数组的中点，将其拆分为[左边界, 中点]和[中点+1, 右边界]两个互不重叠的独立子问题
3. 合并规则：两个子数组的计算结果相加，即为当前子数组的总和

参考Java代码 #

public int sum(int[] arr) {
    // 空数组边界处理
    if (arr == null || arr.length == 0) {
        return 0;
    }
    return sumSplit(arr, 0, arr.length - 1);
}

// 递归计算子数组[begin, end]的总和
private int sumSplit(int[] arr, int begin, int end) {
    // 子数组为空，返回0
    if (begin > end) {
        return 0;
    }
    // 子数组仅含一个元素，终止递归
    if (begin == end) {
        return arr[begin];
    }
    // 避免整数溢出的中点计算方式
    int mid = begin + (end - begin) / 2;
    // 拆分左右子问题，合并结果
    return sumSplit(arr, begin, mid) + sumSplit(arr, mid + 1, end);
}

内容的提问来源于stack exchange，提问作者Thorsten F.