在Python中将数组划分为三个相等的部分
假设我们有一个整数数组A，当且仅当我们可以将该数组划分为三个总和相等的非空部分时，输出才为true。
形式上，如果我们可以找到索引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]）
因此，如果输入为[0,2,1，-6,6，-7,9,1,2,0,1]，则输出为true。三个数组将是[0,2,1]，[-6,6，-7,9,1]和[2,0,1]
为了解决这个问题，我们将遵循以下步骤-
temp：=所有元素的总和，required_sum：=temp/3
设置sum_left来存储从左到右的累计和
设置sum_right来存储从右到左的累计和
index1：=0和index2：=数组长度–1
而index1<index2：
index2：=index2–1
index1：=index1+1
而index1<index2和sum_left[index1]！=required_sum
而index2>index1和sum_right[index2]！=required_sum
如果index1<index2并且index1！=index2，则返回true，否则返回false
示例
让我们看下面的实现以更好地理解-
class Solution(object):
def canThreePartsEqualSum(self, A):
temp = sum(A)
if (temp%3 != 0):
return 0
sum_left=[0 for i in range(len(A))]
sum_left[0] = A[0]
sum_right=[0 for i in range(len(A))]
sum_right[-1] = A[-1]
for i in range(1,len(A)):
sum_left[i] = A[i]+sum_left[i-1]
for i in range(len(A)-2,-1,-1):
sum_right[i] = A[i]+sum_right[i+1]
#print(sum_left,sum_right)
required_sum = temp/3
index1 = 0
index2 = len(A)-1
while index1 < index2:
while index1 <index2 and sum_left[index1]!=required_sum:
index1+=1
while index2>index1 and sum_right[index2]!=required_sum:
index2-=1
return index1<index2 and index1 != index2
ob1 = Solution()print(ob1.canThreePartsEqualSum([0,2,2,-6,6,-7,9,2,2,0,2]))输入值
[0,2,1,-6,6,-7,9,1,2,0,1]
输出结果
true