LeetCode 927. 三等分
题目描述
✅ 927. 三等分
题意分析
将二进制数组切成三个非空连续部分，使它们表示的二进制数值相同。返回
[i,j]时，三部分分别是[0,i]、[i+1,j-1]、[j,n-1]，所以返回的两个下标分别表示第一段末尾和第三段开头。前导零不改变数值，但有效数字后面的零不能省略。不需要把各段转换为整数，只需比较去掉前导零后的二进制表示，避免长度很大时溢出。
解法：定位三段起点 + 三指针同步比较
核心思路
[!blue]
若所有元素都是零，任意非空三段都相等，题目保证长度至少为
3，可直接返回[0,2]。否则三段表示的数为正数，它们去掉前导零后的表示必须完全相同，所以每段包含的1数量也必须相同。总数不是3的倍数时无解。设每段应包含
k个1，三个有效起点就被唯一确定：i1、i2、i3分别是全局第1、第k+1、第2k+1个1的位置。改变切口只能调整前导零，不能改变这三个起点。第三段必须延伸到数组末尾，因此它从
i3开始的有效表示长度固定为L=n-i3，包含全部尾零。前两段从各自有效起点开始，也必须保留完全相同的L位。令三个指针分别从i1、i2、i3同步前进，遇到不同位就无解；第三指针到末尾时，前两段所需的有效表示也比较完了。比较完成后，第一段结束于
p1-1，第二段的有效表示结束于p2-1，所以可以让第三段从p2开始。代码中的end2就是这个结束后一位的下标，实际用作返回的第三段起点。还需保证第一段没有越过i2、第二段没有越过i3，即p1<=i2且p2<=i3。在这些边界成立时，切口到下一有效起点之间只可能是零，分别成为第二、第三段的前导零；三段都含有
k个1，因此非空且数值相同。反过来，起点和有效长度都已固定，逐位比较或边界检查一旦失败，也不可能通过改选切口补救。
解题步骤
- 统计一的数量，处理全零与不能三等分的情况。
- 定位三个有效起点。
- 同步比较三段，从第一个一一直比较到第三段末尾。
- 确认前两段有效表示不重叠，返回第一段末尾与第二段结束后的下标。
同步比较时，
p1、p2始终小于p3，而p3<n才访问数组，因此比较阶段不会越界；范围检查进一步保证得到的是三个不重叠的连续部分。
代码实现
class Solution {
public int[] threeEqualParts(int[] arr) {
int n = arr.length;
int ones = 0;
for (int x : arr) {
if (x == 1) {
ones++;
}
}
// 全零没有有效的一起点，直接返回任意非空三段切法。
if (ones == 0) {
return new int[] {
0,
2
};
}
if (ones % 3 != 0) {
return new int[] {
-1,
-1
};
}
int k = ones / 3;
int i1 = findKthOne(arr, 1);
int i2 = findKthOne(arr, k + 1);
int i3 = findKthOne(arr, 2 * k + 1);
int p1 = i1;
int p2 = i2;
int p3 = i3;
// 第三段必须比较到数组末尾，尾零也属于有效表示。
while (p3 < n) {
if (arr[p1] != arr[p2] || arr[p2] != arr[p3]) {
return new int[] {
-1,
-1
};
}
p1++;
p2++;
p3++;
}
int end1 = p1 - 1;
int start3 = i3;
int lenTail = n - start3;
int end2 = i2 + lenTail;
if (end1 >= i2 || end2 > i3) {
return new int[] {
-1,
-1
};
}
return new int[] {
end1,
end2
};
}
private int findKthOne(int[] arr, int kth) {
int cnt = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
cnt++;
if (cnt == kth) {
return i;
}
}
}
return -1;
}
}
func threeEqualParts(arr []int) []int {
n := len(arr)
ones := 0
for _, x := range arr {
if x == 1 {
ones++
}
}
// 全零没有有效的一起点，直接返回任意非空三段切法。
if ones == 0 {
return []int{
0,
2,
}
}
if ones%3 != 0 {
return []int{
-1,
-1,
}
}
k := ones / 3
i1 := findKthOne(arr, 1)
i2 := findKthOne(arr, k+1)
i3 := findKthOne(arr, 2*k+1)
p1, p2, p3 := i1, i2, i3
// 第三段必须比较到数组末尾，尾零也属于有效表示。
for p3 < n {
if arr[p1] != arr[p2] || arr[p2] != arr[p3] {
return []int{
-1,
-1,
}
}
p1++
p2++
p3++
}
end1 := p1 - 1
lenTail := n - i3
end2 := i2 + lenTail
if end1 >= i2 || end2 > i3 {
return []int{
-1,
-1,
}
}
return []int{
end1,
end2,
}
}
func findKthOne(arr []int, kth int) int {
cnt := 0
for i := 0; i < len(arr); i++ {
if arr[i] == 1 {
cnt++
if cnt == kth {
return i
}
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(n)$，常数次线性扫描。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 比较从第一个一开始，跳过无意义的前导零。
- 第三段末尾固定，决定另外两段需要保留多少尾零。
- 返回下标的两端含义不同：第一段末尾、第三段开头。
易错点总结
[!yellow]
- 只检查一的数量相同：位的排列与尾零也必须一致。
- 全零时继续找第一个一：有效起点不存在。
- 把第三段起点写成第二段末尾：切口偏一，可能漏掉有效位。
- 要求三段长度相同：前导零可以让三段实际长度不同。