Pythonで合計が等しい3つの部分に配列を分割する

整数の配列Aがあるとすると、合計が等しい3つの空でない部分に配列を分割できる場合にのみ、出力はtrueになります。

正式には、（A [0] + A [1] + ... +A[i]がA[i+ 1] + A[と同じであるインデックスi+1

したがって、入力が[0,2,1、-6,6、-7,9,1,2,0,1]の場合、出力はtrueになります。 3つの配列は、[0,2,1]、[-6,6、-7,9,1]、および[2,0,1]

これを解決するには、次の手順に従います-

• temp：=すべての要素の合計、およびrequired_sum：=temp / 3
• sum_leftを設定して累積合計を左から右に保存します
• sum_rightを設定して累積合計を右から左に保存します
• index1：=0およびindex2：=配列の長さ– 1
• while index1
• while index1
• index1：=index1 + 1

例

理解を深めるために、次の実装を見てみましょう-

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