该题解策略首先计算数组中1的总数。如果1的总数不能被3整除,直接返回[-1, -1]。如果整个数组都是0,返回[0, 2]。然后,将数组中1的位置存储在一个列表中,根据1的总数除以3的结果,确定三个部分中每一部分1的起始和结束位置。计算第三部分结束后剩余的0的数量,用这个信息来确定第一部分和第二部分的结束位置。最后,进行一次遍历来确认三部分的内容是否完全相同。如果相同,则返回第一部分和第三部分的结束位置作为结果;如果在任何点不相同,则返回[-1, -1]。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def threeEqualParts(self, arr: List[int]) -> List[int]:
n = len(arr)
cnt = sum(arr) # 计算数组中1的总数
if cnt % 3 != 0:
return [-1, -1] # 如果1的总数不能被3整除,无解
if cnt == 0:
return [0, 2] # 如果数组全为0,任意切分即可
avg = cnt // 3
one_indices = [i for i, x in enumerate(arr) if x == 1] # 存储1的位置
part1_one_start = one_indices[0]
part1_one_end = one_indices[avg - 1]
part2_one_start = one_indices[avg]
part2_one_end = one_indices[avg * 2 - 1]
part3_one_start = one_indices[avg * 2]
part3_one_end = one_indices[-1]
last_zeros = n - 1 - part3_one_end # 计算最后一部分后的0的数量
if part1_one_end + last_zeros >= part2_one_start: # 检查部分之间的重叠
return [-1, -1]
if part2_one_end + last_zeros >= part3_one_start:
return [-1, -1]
part1_end = part1_one_end + last_zeros
part2_end = part2_one_end + last_zeros
part3_start = part2_end + 1
i, j, k = part1_one_start, part2_one_start, part3_one_start
while k < n: # 比较三个部分的内容
if arr[i] == arr[j] == arr[k]:
i += 1
j += 1
k += 1
else:
return [-1, -1]
return [part1_end, part3_start] # 如果比较通过,返回结果