Hard
题目描述
给定一个只包含 0 和 1 的数组 arr，将数组分成三个非空部分，使得所有这些部分表示相同的二进制值。
如果可以做到，请返回任何 [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,0,1,0,0,1]
输出: [0,2]
提示：
3 <= arr.length <= 3 * 10^4arr[i]是 0 或 1
解题思路
这道题要求将数组分成三个相等的二进制数部分。关键思路如下：
核心观察
- 1的个数必须能被3整除：如果总共有
count个1，且count % 3 != 0，则无解 - 特殊情况：如果
count == 0（全为0），任何分割都可以，返回[0, 2] - 每部分必须有
count/3个1：这是三个部分相等的必要条件
解法步骤
- 统计1的总数，检查是否能被3整除
- 找到每部分的第一个1和最后一个1的位置
- 从最后一部分开始比较，因为它决定了尾随0的数量
- 依次比较三个部分是否完全相同（包括0的分布）
实现要点
- 先找到第三部分第一个1的位置，以此为基准
- 逐位比较三个部分，确保每一位都相等
- 返回合适的分割点
[i, j]，其中i是第一部分结束位置，j是第三部分开始位置
时间复杂度O(n)，空间复杂度O(1)，是最优解法。
代码实现
class Solution {
public:
vector<int> threeEqualParts(vector<int>& arr) {
int n = arr.size();
int count = 0;
// 统计1的个数
for (int x : arr) {
count += x;
}
// 如果1的个数不能被3整除，返回无解
if (count % 3 != 0) {
return {-1, -1};
}
// 如果没有1，任意分割都可以
if (count == 0) {
return {0, 2};
}
int target = count / 3;
// 找到第一部分、第二部分、第三部分的第一个1的位置
int first = -1, second = -1, third = -1;
int ones = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 1) {
ones++;
if (ones == 1) first = i;
else if (ones == target + 1) second = i;
else if (ones == 2 * target + 1) third = i;
}
}
// 从第三部分开始比较，确保三部分相等
while (third < n && arr[first] == arr[second] && arr[second] == arr[third]) {
first++;
second++;
third++;
}
if (third == n) {
return {first - 1, second};
}
return {-1, -1};
}
};
class Solution:
def threeEqualParts(self, arr: List[int]) -> List[int]:
n = len(arr)
count = sum(arr)
# 如果1的个数不能被3整除，返回无解
if count % 3 != 0:
return [-1, -1]
# 如果没有1，任意分割都可以
if count == 0:
return [0, 2]
target = count // 3
# 找到第一部分、第二部分、第三部分的第一个1的位置
first = second = third = -1
ones = 0
for i in range(n):
if arr[i] == 1:
ones += 1
if ones == 1:
first = i
elif ones == target + 1:
second = i
elif ones == 2 * target + 1:
third = i
# 从第三部分开始比较，确保三部分相等
while third < n and arr[first] == arr[second] == arr[third]:
first += 1
second += 1
third += 1
if third == n:
return [first - 1, second]
return [-1, -1]
public class Solution {
public int[] ThreeEqualParts(int[] arr) {
int n = arr.Length;
int count = 0;
// 统计1的个数
foreach (int x in arr) {
count += x;
}
// 如果1的个数不能被3整除，返回无解
if (count % 3 != 0) {
return new int[] {-1, -1};
}
// 如果没有1，任意分割都可以
if (count == 0) {
return new int[] {0, 2};
}
int target = count / 3;
// 找到第一部分、第二部分、第三部分的第一个1的位置
int first = -1, second = -1, third = -1;
int ones = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 1) {
ones++;
if (ones == 1) first = i;
else if (ones == target + 1) second = i;
else if (ones == 2 * target + 1) third = i;
}
}
// 从第三部分开始比较，确保三部分相等
while (third < n && arr[first] == arr[second] && arr[second] == arr[third]) {
first++;
second++;
third++;
}
if (third == n) {
return new int[] {first - 1, second};
}
return new int[] {-1, -1};
}
}
var threeEqualParts = function(arr) {
const n = arr.length;
const ones = arr.reduce((sum, val) => sum + val, 0);
if (ones === 0) {
return [0, 2];
}
if (ones % 3 !== 0) {
return [-1, -1];
}
const onesPerPart = ones / 3;
// Find positions of ones
const onePositions = [];
for (let i = 0; i < n; i++) {
if (arr[i] === 1) {
onePositions.push(i);
}
}
// Find the start of each part (first 1 in each part)
const start1 = onePositions[0];
const start2 = onePositions[onesPerPart];
const start3 = onePositions[2 * onesPerPart];
// Check if the three parts have the same pattern of 1s and 0s
while (start3 < n && arr[start1] === arr[start2] && arr[start2] === arr[start3]) {
start1++;
start2++;
start3++;
}
if (start3 === n) {
return [start1 - 1, start2];
}
return [-1, -1];
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(1) |