LeetCode 1013. 将数组分成和相等的三个部分

2026-04-17 HGNULB 约 5 分钟

文章信息 9 个分类 2 个标签

分类

LeetCode CodeTop 简单未解决 5-10 字节跳动微软阿里巴巴腾讯

题目描述

✅ 1013. 将数组分成和相等的三个部分

题意分析

题目只要一个布尔值：能不能在数组里切两刀，把它劈成三段连续且非空的部分，使三段的元素和完全相等。注意切的是下标区间，不是任意挑元素，所以三段的相对顺序是固定的，问题的自由度只剩下两个切点的位置。

数组长度可以到 $5 \times 10^4$，两个切点的组合有 $O(n^2)$ 种，逐对枚举再求和是 $O(n^3)$、前缀和优化后也要 $O(n^2)$，在这个规模下已经明显偏慢，约束在暗示我们只应该扫一遍数组。

元素范围是 -10^4 <= arr[i] <= 10^4，允许负数和零，这一点是本题所有坑的来源：前缀和不再单调递增，"和超过目标就往回缩"这类基于单调性的窗口技巧全部失效；同时目标段和可能等于 0，会出现大量长度不一的合法切法。

边界上要留意：数组长度至少为 3 才谈得上切三段；三段都必须非空，不能出现"第三段是空的"这种取巧答案；总和是三段之和，所以总和一定是段和的 3 倍。

解法：贪心确定前两个分段

核心思路

若三段和相等，数组总和 total 必须能被 3 整除，每段目标和为 target = total / 3。

从左向右累加当前段，第一次达到 target 时立即切开并重新计数；找到两个切点后，剩余部分的和自动是 total - 2 * target = target。

取最早可用切点是安全的：如果存在更晚的合法切点，提前结束当前段只会给后续分段留下更多元素，不会越过原本的第二切点。扫描只进行到倒数第二个元素，保证第三段非空。

数组允许负数，不能在当前和超过目标时提前停止；算法只判断是否恰好等于目标，不依赖前缀和单调性。

解题步骤

计算总和；若 total % 3 != 0，返回 false。

令 target = total / 3，扫描前 n - 1 个元素并累加 sum。

当 sum == target 时确定一个切点，分段数加一，并把 sum 清零。

找到两个切点立即返回 true；否则扫描结束后返回 false。

例如 [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1] 的总和为 9。扫描得到前两段和都为 3，剩余后缀总和也必为 3，因此可以三等分。

代码实现

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        long total = 0;
        for (int num : arr) {
            total += num;
        }
        if (total % 3 != 0) {
            return false;
        }

        long target = total / 3;
        long sum = 0;
        int parts = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            sum += arr[i];
            if (sum == target) {
                parts++;
                sum = 0;
                if (parts == 2) {
                    return true;
                }
            }
        }
        return false;
    }
}

func canThreePartsEqualSum(arr []int) bool {
    var total int64
    for _, num := range arr {
        total += int64(num)
    }
    if total%3 != 0 {
        return false
    }

    target := total / 3
    var sum int64
    parts := 0
    for i := 0; i < len(arr)-1; i++ {
        sum += int64(arr[i])
        if sum == target {
            parts++
            sum = 0
            if parts == 2 {
                return true
            }
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(n)$，求总和与寻找分段各线性扫描一次。

空间复杂度：$O(1)$，只保存若干计数变量。

关键点总结

先用总和确定唯一目标段和，再贪心选择最早的两个切点。

只需确认前两段，第三段由总和守恒自动成立。

循环不能扫描最后一个元素，否则可能把第三段切成空段。

负数会破坏单调性，但不影响“累加到目标就切分”的判断。

使用更宽的整数类型保存累加和，避免溢出。

易错点总结

总和不能被 3 整除时仍继续分段，会基于截断后的错误目标计算。

找到一个目标段就返回真；题目需要两个切点和三个非空区间。

扫描包含最后一个元素，target == 0 时尤其容易把空后缀当成第三段。

达到目标后没有把当前段和清零，下一段会继续累加全局前缀。

因为当前和暂时超过目标就提前失败；后续负数仍可能把它拉回目标。

在 target == 0 时让同一位置重复计数；每次命中后必须继续到下一个元素。

相似题目

题目	难度	考察点
724. 寻找数组的中心下标	简单	只切一刀，用前缀和与总和的关系直接定位平衡点
560. 和为 K 的子数组	中等	目标和不固定，需要哈希表记录前缀和出现次数
523. 连续的子数组和	中等	判定条件从"等于目标"换成"前缀和同余"
416. 分割等和子集	中等	分出的两部分不要求连续，退化为 0-1 背包可行性
410. 分割数组的最大值	困难	段数给定但和不必相等，改为二分答案加贪心校验