What is the main challenge in the Three Equal Parts problem?

The primary challenge is aligning three segments of a binary array so that each represents the same integer value, handling leading zeros, and ensuring proper index calculation.

How do I handle arrays with zero ones?

If the array contains only zeros, any split producing three non-empty parts is valid because all segments represent the integer zero.

Does the order of elements in arr matter?

Yes, the original order must be preserved; the three parts must be contiguous subarrays maintaining the original sequence.

Can this solution scale to large arrays?

Yes, the approach is linear O(n) in time and constant O(1) extra space, making it efficient for arrays up to 3 * 10^4 elements.

How do trailing zeros affect the solution?

Trailing zeros at the end of segments must match to ensure the binary values are equal, so split indices should account for them carefully.

#927

Hard

auto_awesome数组·数学

LeetCode 题解工作台

三等分

给定一个由 0 和 1 组成的数组 arr ，将数组分成 3 个非空的部分，使得所有这些部分表示相同的二进制值。如果可以做到，请返回任何 [i, j] ，其中 i+1 ，这样一来： arr[0], arr[1], ..., arr[i] 为第一部分； arr[i + 1], arr[i + 2…

数组数学

题目描述

给定一个由 0 和 1 组成的数组 arr ，将数组分成 3 个非空的部分 ，使得所有这些部分表示相同的二进制值。

如果可以做到，请返回任何 [i, j]，其中 i+1 < j，这样一来：

arr[0], arr[1], ..., arr[i] 为第一部分；
arr[i + 1], arr[i + 2], ..., arr[j - 1] 为第二部分；
arr[j], arr[j + 1], ..., arr[arr.length - 1] 为第三部分。
这三个部分所表示的二进制值相等。

如果无法做到，就返回 [-1, -1]。

注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，[1,1,0] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的，所以 [0,1,1] 和 [1,1] 表示相同的值。

示例 1：

输入：arr = [1,0,1,0,1]
输出：[0,3]

示例 2：

输入：arr = [1,1,0,1,1]
输出：[-1,-1]

示例 3:

输入：arr = [1,1,0,0,1]
输出：[0,2]

提示：

3 <= arr.length <= 3 * 10⁴
arr[i] 是 0 或 1

lightbulb

解题思路

方法一：计数 + 三指针

我们记数组的长度为 $n$ ，数组中 $1$ 的数量为 $cnt$ 。

显然 $cnt$ 必须是 $3$ 的倍数，否则无法将数组三等分，可以提前返回 $[-1, -1]$ 。如果 $cnt$ 为 $0$ ，那么意味着数组中所有元素都为 $0$ ，直接返回 $[0, n - 1]$ 即可。

我们将 $cnt$ 除以 $3$ ，得到每一份中 $1$ 的数量，然后找到每一份的第一个 $1$ 在数组 arr 中的位置（参考以下代码中的 $find(x)$ 函数），分别记为 $i$ , $j$ , $k$ 。

0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0
  ^         ^             ^
  i         j             k

接着我们从 $i$ , $j$ , $k$ 开始往后同时遍历每一部分，判断三部分对应的值是否相等，是则继续遍历，直至 $k$ 到达 $arr$ 末尾。

0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0
          ^         ^             ^
          i         j             k

遍历结束时，若 $k=n$ ，说明满足三等分，返回此时的 $[i - 1, j]$ 作为答案，否则返回 $[-1, -1]$ 。

时间复杂度 $O(n)$ ，其中 $n$ 表示 arr 的长度。空间复杂度 $O(1)$ 。

相似题目：

1573. 分割字符串的方案数

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        def find(x):
            s = 0
            for i, v in enumerate(arr):
                s += v
                if s == x:
                    return i

        n = len(arr)
        cnt, mod = divmod(sum(arr), 3)
        if mod:
            return [-1, -1]
        if cnt == 0:
            return [0, n - 1]

        i, j, k = find(1), find(cnt + 1), find(cnt * 2 + 1)
        while k < n and arr[i] == arr[j] == arr[k]:
            i, j, k = i + 1, j + 1, k + 1
        return [i - 1, j] if k == n else [-1, -1]

speed

复杂度分析

指标	值
时间	complexity is O(n) for single-pass counting and alignment checks, where n is the length of the array. Space complexity is O(1) additional memory if segments are compared via indices without extra arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checking if total ones count is divisible by three is crucial.
question_mark
Careful handling of leading zeros distinguishes correct from incorrect partitions.
question_mark
Aligning segments from the last one backwards helps validate equality efficiently.

warning

常见陷阱

外企场景

error
Assuming leading zeros affect integer comparison, which can cause wrong splits.
error
Forgetting to handle arrays with zero ones as a valid equal split.
error
Incorrectly computing indices when trailing zeros are required for alignment.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Partition a binary array into k equal-value parts instead of three, requiring generalization of ones distribution.
arrow_right_alt
Find the minimal length of the first part to achieve three equal binary values for optimization problems.
arrow_right_alt
Allowing arrays with non-binary integers and defining equality via decimal value rather than binary string comparison.

help

常见问题

外企场景

继续练习

#932 漂亮数组 #939 最小面积矩形 #914 卡牌分组