数组分割最小绝对差值求解：优化O(N²)算法需求

阿华AIGC实验室

2026-5-14

高效解决磁带分割最小差值问题

问题回顾

给定一个由N个整数组成的非空数组A，数组A代表磁带上的数字。任意满足0 < P < N的整数P可将磁带分为两个非空部分：A[0], A[1], ..., A[P−1]和A[P], A[P+1], ..., A[N−1]。两部分的差值为：|(A[0]+A[1]+…+A[P−1]) − (A[P]+A[P+1]+…+A[N−1])|，即两部分和的绝对差值。
示例：数组A为[3,1,2,4,3]，可在4处分割：
P=1，差值=|3−10|=7；
P=2，差值=|4−9|=5；
P=3，差值=|6−7|=1；
P=4，差值=|10−3|=7。
需返回最小差值1。
约束条件：
N的范围是[2, 100000]；
数组A的每个元素取值范围是[-1000, 1000]。

你的现有解法问题

你当前的思路方向是对的，但嵌套循环的写法导致时间复杂度达到O(N²)——每次计算右部分和都要重新遍历剩余数组。当N接近10万时，这种方法的运算量会突破10^10次，完全无法在合理时间内完成，必须优化到线性时间复杂度**O(N)**才行。

高效解法思路

核心逻辑

其实我们不需要反复计算右部分的和，利用数组总和可以快速推导：

先算出整个数组的总和totalSum；
遍历数组时，逐步累加得到左部分的和leftSum；
右部分的和直接用totalSum - leftSum计算，省去重复遍历；
每次计算当前分割的差值，同时记录最小的那个差值。

整个过程只需要两次遍历数组（一次算总和，一次算分割差值），甚至可以合并成一次遍历，时间复杂度是O(N)，空间复杂度是O(1)，完全符合题目要求。

示例推导（以`[3,1,2,4,3]`为例）

总和totalSum = 3+1+2+4+3 = 13
逐个计算分割点：
- P=1：leftSum=3，差值=|3 - (13-3)|=7
- P=2：leftSum=3+1=4，差值=|4 -9|=5
- P=3：leftSum=4+2=6，差值=|6-7|=1
- P=4：leftSum=6+4=10，差值=|10-3|=7
最终最小差值就是1，和示例结果一致。

Java代码实现

class Solution {
    public int solution(int[] A) {
        // 用long避免整数溢出，防止大数组累加时超出int范围
        long totalSum = 0;
        for (int num : A) {
            totalSum += num;
        }
        
        long leftSum = 0;
        long minDiff = Long.MAX_VALUE;
        
        // 遍历到倒数第二个元素即可，保证右部分至少有一个元素
        for (int i = 0; i < A.length - 1; i++) {
            leftSum += A[i];
            long rightSum = totalSum - leftSum;
            long currentDiff = Math.abs(leftSum - rightSum);
            // 更新最小差值
            if (currentDiff < minDiff) {
                minDiff = currentDiff;
            }
        }
        
        return (int) minDiff;
    }
}