文章作者:Tyan
博客:noahsnail.com | CSDN | 简书
1. Description
Three Equal Parts2. Solution
解析:Version 1,由于数组分为三部分,因此各部分中1
的个数相等是三部分相等的前提条件之一,因此先计算数组的总和,如果和为0
,则i,j
的位置是满足二者关系的任意位置,因此直接返回最简单的[0,2]
即可,如果总和除3
的余数不为0
,则一定构不成三部分相等,直接返回[-1,-1]
,否则,则根据三部分1
的个数将数组先分为三部分,由于三部分第一个1
之前的0
都无效,因此,将i,j,k
三部分分别定位到第一个1
的位置,由于最后一部分最后一个1
之后的0
是有效位,因此遍历区间为第三部分的第一个1
到最后一位,第一部分及第二部分的对应位置上的数字应该都与第三部分对应位置的数字相等,如果不相等,则不能分隔数组,最后根据对应的位置关系,返回[i-1,j]
即可。Version 2直接通过index
方法来获取三部分的第一个1
。
- Version 1
class Solution:
def threeEqualParts(self, arr: List[int]) -> List[int]:
total = sum(arr)
if total == 0:
return [0, 2]
if total % 3 != 0:
return [-1, -1]
n = total // 3
count = 0
for index in range(len(arr)):
if arr[index] == 1:
count += 1
if count == 1:
i = index
elif count == n + 1:
j = index
elif count == 2 * n + 1:
k = index
while k < len(arr):
if arr[i] == arr[j] and arr[j] == arr[k]:
i += 1
j += 1
k += 1
else:
return [-1, -1]
return [i-1, j]
网友评论