0927. Three Equal Parts

题目信息

题号:

0927

难度:

Hard

主题:

二进制数组、连续分割、前导零

原题:

LeetCode 0927

重点:

返回下标 [i, j] 后三段分别是 arr[0..i]、arr[i+1..j-1]、arr[j..n-1];三段非空且表示的二进制值相等,前导零允许存在

题目重述

给定只包含 0 和 1 的数组 arr。寻找两个下标 i 和 j,使 0 <= i < i + 1 < j < arr.length,并把数组分为三个非空连续部分:arr[0..i]、arr[i+1..j-1] 和 arr[j..arr.length-1]。

把每一部分按二进制表示解释为整数,允许存在任意数量的前导零。若三个整数相等,返回任意一组 [i, j];若不存在合法分割,返回 [-1, -1]。

3 <= arr.length <= 3 * 10^4。

自建示例

三段都表示二进制 10:

输入:arr = [0,1,0,1,0,1,0]
输出:[2,5]
解释:三段分别为 [0,1,0]、[1,0]、[1,0],忽略前导零后都表示十进制 2。其他合法下标组合也可以返回。

全部元素都是零:

输入:arr = [0,0,0]
输出:[0,2]
解释:三段分别是 [0]、[0]、[0],都表示数值 0;这是最短数组的一组合法分割。