LeetCode 1013. 将数组分成和相等的三个部分
题目描述
题意分析
将整个数组切成三个连续、非空的部分，使三段元素和相等，判断能否做到。每个元素必须属于其中一段，不能重排或跳过元素；只需要返回是否可行，不需要输出切点。
数组可以包含正数、负数和零。若总和不能被三整除，必定无法划分；若能整除，每一段的目标和就确定为
total / 3。找到前两段后，剩余部分的和虽然自动等于目标，仍须保证它至少有一个元素。
解法：贪心确定前两个分段
核心思路
[!blue]
从左向右累加当前段的和，第一次等于目标时就结束第一段；清零后，从下一项开始寻找第二段。找到两段后，总和减去这两段便得到第三段的和，因此无需再单独寻找第三段的结束位置。
为什么第一段可以取最早的切点？假设存在一种合法划分，第一段结束在更靠后的位置。最早切点之前的和与这个合法第一段的和都等于目标，所以两个切点之间的额外部分和为零。把这段零和部分留给第二段，不会改变第二段的和，原来的第二个切点仍然可用。因此提前结束第一段不会破坏原本存在的可行方案。
第一段确定后，第二段也取最早达到目标的位置。它不会晚于任何可行的第二切点；如果原来存在非空第三段，提前结束第二段仍然会留下非空后缀。总和守恒又保证这段后缀的和等于目标，所以这次贪心选择同样安全。
代码只扫描到倒数第二个元素，专门为第三段保留至少一个位置。每段都在读入至少一个元素后才能计数，即使目标为零，也不会把空段算作完成。找到第二段立即返回真；扫描结束仍找不到两段则返回假。
这个证明依赖相同前缀和之间的差为零，不依赖段和随扫描单调变化。因此允许负数，当前段和暂时超过目标也不能提前判失败。
解题步骤
- 扫描数组求总和，不可被三整除时返回
false。- 令目标和为总和的三分之一，当前段和、已完成段数都从零开始。
- 从下标
0扫描到n - 2，不断加入当前元素。- 当前段和等于目标时，将段数加一并清零段和；段数达到二时返回
true。- 循环结束后仍未找到两段，返回
false。
代码实现
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)$，只保存总和、目标、当前段和及段数。
关键点总结
[!green]
- 只需确定两刀，第三段的目标和由总和自动保证，非空性由扫描上界保证。
- 最早切点与更晚的可行切点之间和为零，因此提前切分不会破坏后续可行性。
- 每个新段从下一个元素重新累加，目标为零时也能保证三段都非空。
易错点总结
[!yellow]
- 扫描包括最后一个元素，可能在数组末尾完成第二段，错误地留下空第三段。
- 总和可被三整除只是必要条件，还要找到两个合法切点，不能直接返回真。
- 找到一段就返回，还没有完成第二刀，也不能保证剩余两段能够平分。
- 完成一段后不清零段和，会把后续判断误变成前缀和判断，与当前状态定义不一致。
- 当前和超过目标时就停止，会漏掉后续负数抵消后重新达到目标的情况。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！