原文链接: https://leetcode-cn.com/problems/three-equal-parts

英文原文

You are given an array arr which consists of only zeros and ones, divide the array into three non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i + 1 < j, such that:

• arr[0], arr[1], ..., arr[i] is the first part,
• arr[i + 1], arr[i + 2], ..., arr[j - 1] is the second part, and
• arr[j], arr[j + 1], ..., arr[arr.length - 1] is the third part.
• All three parts have equal binary values.

If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

 

Example 1:

Input: arr = [1,0,1,0,1]
Output: [0,3]

Example 2:

Input: arr = [1,1,0,1,1]
Output: [-1,-1]

Example 3:

Input: arr = [1,1,0,0,1]
Output: [0,2]

 

Constraints:

• 3 <= arr.length <= 3 * 104
• arr[i] is 0 or 1

中文题目

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

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

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

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

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

 

示例 1：

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

示例 2：

输出：[1,1,0,1,1]
输出：[-1,-1]

 

提示：

1. 3 <= A.length <= 30000
2. A[i] == 0 或 A[i] == 1

 

通过代码

官方题解

方法一： 将 1 的数量三等分

思路

如果存在这种分法，那么最终每一部分 1 的数量一定是相等的。下面给出的算法也是基于这个思路。

算法

设 S 为 A 中 1 的个数，最终每一块 1 的数量是相同的，那么每一块都有 T = S / 3 个 1。

如果 S 不能被 3 整除，显然不存在这种分法。

可以简单地找到 A 中第 1 个，第 T 个，第 T+1 个，第 2T 个，第 2T+1 个，第 3T 个 1。这些位置形成了三个区间，[i1, j1], [i2, j2], [i3, j3]。（如果只有 3 个 1，每个区间的大小为 1）。

除去这三个区间，可能还有一些后缀 0。0 的数量由 j3 之后有多少 0 来决定，j3 之后 0 的数量为 z = S.length - j3。

加上后缀 0 之后，第一部分 [i1, j1] 就变成了 [i1, j1+z]，同样第二部分 [i2, j2] 也变成了 [i2, j2+z]。

如果这三个区间都合法，那么答案就是 [j1+z, j2+z+1]。

[solution1-Java]
class Solution {
    public int[] threeEqualParts(int[] A) {
        int[] IMP = new int[]{-1, -1};
        int N = A.length;

        int S = 0;
        for (int x: A) S += x;
        if (S % 3 != 0) return IMP;
        int T = S / 3;
        if (T == 0)
            return new int[]{0, N - 1};

        int i1 = -1, j1 = -1, i2 = -1, j2 = -1, i3 = -1, j3 = -1;
        int su = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] == 1) {
                su += 1;
                if (su == 1) i1 = i;
                if (su == T) j1 = i;
                if (su == T+1) i2 = i;
                if (su == 2*T) j2 = i;
                if (su == 2*T + 1) i3 = i;
                if (su == 3*T) j3 = i;
            }
        }

        // The array is in the form W [i1, j1] X [i2, j2] Y [i3, j3] Z
        // where [i1, j1] is a block of 1s, etc.
        int[] part1 = Arrays.copyOfRange(A, i1, j1+1);
        int[] part2 = Arrays.copyOfRange(A, i2, j2+1);
        int[] part3 = Arrays.copyOfRange(A, i3, j3+1);

        if (!Arrays.equals(part1, part2)) return IMP;
        if (!Arrays.equals(part1, part3)) return IMP;

        // x, y, z: the number of zeros after part 1, 2, 3
        int x = i2 - j1 - 1;
        int y = i3 - j2 - 1;
        int z = A.length - j3 - 1;

        if (x < z || y < z) return IMP;
        return new int[]{j1+z, j2+z+1};
    }
}

[solution1-Python]
class Solution(object):
    def threeEqualParts(self, A):
        IMP = [-1, -1]

        S = sum(A)
        if S % 3: return IMP
        T = S / 3
        if T == 0:
            return [0, len(A) - 1]

        breaks = []
        su = 0
        for i, x in enumerate(A):
            if x:
                su += x
                if su in {1, T+1, 2*T+1}:
                    breaks.append(i)
                if su in {T, 2*T, 3*T}:
                    breaks.append(i)

        i1, j1, i2, j2, i3, j3 = breaks

        # The array is in the form W [i1, j1] X [i2, j2] Y [i3, j3] Z
        # where [i1, j1] is a block of 1s, etc.
        if not(A[i1:j1+1] == A[i2:j2+1] == A[i3:j3+1]):
            return [-1,-1]

        # x, y, z: the number of zeros after part 1, 2, 3
        x = i2 - j1 - 1
        y = i3 - j2 - 1
        z = len(A) - j3 - 1

        if x < z or y < z: return IMP
        j1 += z
        j2 += z
        return [j1, j2+1]

复杂度分析

• 时间复杂度： $O(N)$，其中 $N$ 为 S 的长度。

• 空间复杂度： $O(N)$。

统计信息

通过次数	提交次数	AC比率
3588	10550	34.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言