LeetCode 927. 三等分

2021-04-16 HGNULB 约 12 分钟

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

分类

题目描述

✅ 927. 三等分

题意分析

给一个只含 0 和 1 的数组，把它切成三个非空的连续段，要求三段各自当作二进制数（高位在左）时数值相等。返回两个下标 [i, j]，含义是第一段为 arr[0..i]、第二段为 arr[i+1..j-1]、第三段为 arr[j..n-1]；无解返回 [-1, -1]。

返回值的定义要先抠清楚：给的是第一段的结尾和第三段的开头，第二段夹在中间，因此必须满足 i + 1 <= j - 1，即 j >= i + 2。三段都不能为空。

「二进制值相等」这个条件有两层含义，必须拆开看。第一层，三段中 1 的个数必须相同——因为把每段的前导 0 去掉后剩下的比特串完全决定了数值，而不同数量的 1 无论如何排不出相同的数。所以 1 的总数必须能被 3 整除，否则直接无解。

第二层，也是这题真正的难点：前导 0 无所谓，但末尾 0 至关重要。0011 和 11 数值相同，但 110 和 11 不同。所以三段从各自「第一个 1」开始一直到该段结尾的比特序列必须逐位一致，包括结尾有多少个 0。

约束里 $n$ 最大 3 万，$O(n)$ 或 $O(n \log n)$ 都行，但显然不需要复杂结构——所有判定都能在常数次线性扫描里完成。

边界：数组全是 0 时，任意切法三段都是 0，直接返回一个合法切法（如 [0, 2]，此时 $n \ge 3$ 由题目保证）；1 的个数不是 3 的倍数时无解；1 的个数是 3 的倍数但排布不一致时同样无解。

解法：定位三段起点 + 三指针同步比较

核心思路

暴力做法是枚举两个切点 (i, j)，对每种切法算出三段的数值再比较。切点对有 $O(n^2)$ 种，每种还要 $O(n)$ 比较，总共 $O(n^3)$；即便用哈希或前缀技巧优化比较，$O(n^2)$ 的枚举在 3 万规模下也是 9 亿次，不可行。

瓶颈在于我们把切点当成了自由变量去搜索。但仔细想：既然三段的 1 的个数必须各为 k = ones / 3，那么每段的第一个 1 分别是全局第 1 个、第 k+1 个、第 2k+1 个 1——这三个位置是唯一确定的，根本不用枚举。

记这三个下标为 i1、i2、i3。三段去掉前导 0 后的有效部分，分别从 i1、i2、i3 开始。既然三段数值相等，这三段有效部分必须逐位完全相同且长度相同。而第三段的有效部分一直延伸到数组末尾，长度固定为 L = n - i3。所以另外两段的有效部分也必须是 L 位，且逐位与之相同。

于是校验方式变得极简：三个指针 p1 = i1、p2 = i2、p3 = i3 同步右移，每步要求 arr[p1] == arr[p2] == arr[p3]，直到 p3 走出数组。任何一位不相等，立即判无解。

不变量：循环的每一轮开始时，arr[i1..p1-1]、arr[i2..p2-1]、arr[i3..p3-1] 三段完全相同且长度相等（都等于 p3 - i3）。循环自然结束时这个长度恰好是 L，三段有效部分校验完毕。

校验通过后还要把切点算出来。第一段必须至少覆盖到 i1 + L - 1（有效部分的末位），所以取 end1 = i1 + L - 1。第三段的开头可以往前挪，因为挪进来的都是前导 0、不改变数值；最靠前的合法位置是 end2 = i2 + L——第二段的有效部分到 i2 + L - 1 结束，从下一位起就归第三段。

最后还需两道合法性检查。end1 < i2：第一段不能吃掉第二段的第一个 1。end2 <= i3：第三段的起点不能越过第三段的第一个 1。两者任一不满足，说明三段区域发生重叠，无解。这两个检查不是可选的补丁——当 1 的分布过于密集时，逐位比较可能通过但区域切不开。

解题步骤

统计 1 的总数 ones：这是所有后续判断的前提，一次线性扫描。

ones == 0 直接返回 [0, 2]：全 0 数组的任意切法都合法（三段都是 0），题目保证 $n \ge 3$，所以 [0, 2] 一定是合法切法。这个分支必须写在前面——后面的逻辑依赖「存在 1」这个前提，findKthOne 在全 0 时会返回 -1，直接进入后续会越界。

ones % 3 != 0 返回 [-1, -1]：三段 1 的个数必须相同，不能整除就无解，提前退出。

令 k = ones / 3，定位 i1、i2、i3：分别是第 1 个、第 k+1 个、第 2k+1 个 1 的下标，也就是三段有效部分的起点。k+1 与 2k+1 的偏移量是全题最容易写错的地方——是「下一段的第一个 1」，不是「第 k 个」。

三指针同步比较：p1/p2/p3 从三个起点出发同步右移，循环条件是 p3 < n。用 p3 作主导是因为它最先到达数组末尾；p1、p2 在此期间必然不越界（它们始终小于 p3）。

任一位不等立即返回 [-1, -1]：三段的有效比特必须逐位一致，包含末尾的 0。

计算切点：end1 = p1 - 1（循环结束时 p1 = i1 + L，减一即第一段有效部分的末位）；L = n - i3；end2 = i2 + L（第二段有效部分结束后的第一个位置）。

区域合法性检查 end1 >= i2 || end2 > i3 则无解：前者说明第一段侵入了第二段的第一个 1，后者说明第三段起点越过了自己的第一个 1，两种情况都无法真正切开。

返回 [end1, end2]。

以 arr = [1,0,1,0,1] 走一遍，n = 5。

统计得 ones = 3，非 0 且能被 3 整除，k = 1。定位起点：第 1 个 1 在下标 0，所以 i1 = 0；第 2 个 1（即 k+1 = 2）在下标 2，i2 = 2；第 3 个 1（即 2k+1 = 3）在下标 4，i3 = 4。

三指针从 (0, 2, 4) 出发。第 1 轮：arr[0] = arr[2] = arr[4] = 1，一致，推进到 (1, 3, 5)。此时 p3 = 5 不小于 n = 5，循环结束。

计算切点：end1 = p1 - 1 = 0；L = n - i3 = 5 - 4 = 1；end2 = i2 + L = 2 + 1 = 3。

合法性检查：end1 = 0 不大于等于 i2 = 2，通过；end2 = 3 不大于 i3 = 4，通过。返回 [0, 3]。

验证：第一段 arr[0..0] = [1] 值为 1；第二段 arr[1..2] = [0,1] 值为 1；第三段 arr[3..4] = [0,1] 值为 1。三者相等，正确。注意第二段和第三段各自带了一个前导 0，这正是「前导 0 不影响数值」的体现——我们从 i2、i3 开始比较而不是从段首开始，就是为了绕开这些无关的 0。

再看一个无解用例 arr = [1,1,1,0,0,0]。ones = 3，k = 1，i1 = 0、i2 = 1、i3 = 2，L = 6 - 2 = 4。三指针从 (0,1,2) 出发：第 1 轮 arr[0]=arr[1]=arr[2]=1，一致，推进到 (1,2,3)；第 2 轮 arr[1] = 1、arr[2] = 1、arr[3] = 0，不一致，返回 [-1,-1]。这个结论是对的——第三段末尾拖着三个 0，数值至少是 8，而前两段的 1 都在高位挤在一起，无论怎么切都凑不出相等的三个值。这也说明为什么末尾 0 必须参与比较：如果只比较「1 的相对位置」，这个用例会被误判为有解。

代码实现

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)$。统计 1 的总数扫一遍，定位三个起点最多再扫三遍（每次都是线性），三指针同步比较最多走 $n$ 步。所有步骤都是常数次线性扫描，不含任何枚举切点的嵌套循环。

空间复杂度：$O(1)$。只用了若干下标与计数变量，返回的长度为 2 的数组是结果本身，不计入额外开销。

关键点总结

「若干段数值相等」的题，先把不变量提取出来：本题是「每段 1 的个数必须相同」，由此立刻得到整除性判定和三段起点的唯一定位，把 $O(n^2)$ 的切点枚举压成 $O(1)$ 的算术。

二进制比较里前导 0 与末尾 0 的地位截然不同：前导 0 可以随便加，末尾 0 直接决定数量级。识别出这个不对称性，才知道该从第一个 1 开始比、比到末尾为止。

第三段的有效长度 L = n - i3 是全题的标尺——它一确定，另外两段该比多少位、切点落在哪里全都被推导出来，不需要任何试探。

全 0 是必须前置处理的特例：它让「第一个 1」不存在，后续所有推导的前提都不成立。凡是依赖「找第一个某元素」的算法，都要先问一句「不存在时怎么办」。

逐位比较通过还不够，必须再检查三段区域是否真的能切开（end1 < i2 且 end2 <= i3）。比较验证的是「数值相等」，区域检查验证的是「切法存在」，两件事不能互相替代。

面试视角：这题的表述像模拟题，实则是观察题。答题时先说「1 的个数必须三等分」，再说「前导 0 无关、末尾 0 关键」，最后才落到三指针——推导链条比代码重要得多。

易错点总结

不特判全 0 数组：[0,0,0] 中 findKthOne 返回 -1，随后 arr[-1] 直接越界异常；正确答案是任意合法切法如 [0,2]。

只比较 1 的相对位置、忽略末尾 0：[1,1,1,0,0,0] 中三段各有一个 1 且「间距」看似可对齐，会被误判为有解，正确答案是 [-1,-1]。

起点偏移写成第 k 个而不是第 k+1 个 1：[1,0,1,0,1] 中 k = 1，若把 i2 取成第 1 个 1（下标 0）就与 i1 重合，三指针从同一位置出发，比较必然通过但切点算出来会重叠，返回错误的 [-1,-1] 或非法下标。

循环条件用 p1 < n 或 p2 < n：p1、p2 比 p3 小，用它们作条件会让 p3 越过数组末尾，arr[p3] 越界。必须用最靠右的 p3。

省掉 end1 >= i2 || end2 > i3 的区域检查：1 分布密集时逐位比较可能通过，但三段区域重叠，返回的下标会让某一段为空或与相邻段交叉，判题直接判错。

end2 写成 i2 + L - 1：返回的是第三段的起点而不是第二段的终点，少 1 会把第二段有效部分的末位划给第三段，[1,0,1,0,1] 会返回 [0,2]，此时第二段变成 arr[1..1] = [0] 值为 0，与其余两段不等。

end1 写成 i1 + L：多算一位会让第一段吞掉第二段的前导 0 甚至第一个 1，[1,1,0,0,1] 这类紧凑输入会直接触发区域检查失败，误报无解。

误以为三段长度必须相等：[1,0,1,0,1] 的正确切法是长度 1、2、2，段长可以不同；按等长切会漏掉绝大多数有解用例。

把三段真的转成整数再比较：$n$ 可达 3 万，二进制转十进制会溢出任何内建整数类型；必须在比特层面比较。

ones % 3 != 0 时忘记提前返回：继续走下去 k 会算错，三个起点定位到错误位置，比较结果不可预测。

返回值语义搞反：题目要的是「第一段结尾」和「第三段开头」，若返回「第一段结尾」和「第二段结尾」，[1,0,1,0,1] 会返回 [0,2] 而不是 [0,3]。

相似题目

题目	难度	考察点
1013. 将数组分成和相等的三个部分	简单	判据是「和的三分之一」而非比特序列，一遍扫描累加即可，无前导零陷阱
416. 分割等和子集	中等	划分不要求连续，退化成子集和问题，必须用 01 背包而非扫描
410. 分割数组的最大值	困难	同为连续段划分，但目标是最小化最大段和，用二分答案配合贪心判定
861. 翻转矩阵后的得分	中等	同样把 0/1 序列当二进制数看，靠位权决定决策优先级，考的是高位的支配性