在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