在 Python 中将数组分成三部分，且总和相等

pythonserver side programmingprogramming更新于 2025/11/2 9:16:17

假设我们有一个整数数组 A，当且仅当我们能将数组分成三个非空部分，且总和相等时，我们的输出才会为真。

正式地，如果我们能找到索引 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]，则输出为真。三个数组将是 [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 < index2:
- while index1 < index2 和 sum_left[index1] != required_sum
  - index1 := index1 + 1
- while index2 > index1 和 sum_right[index2] != required_sum
  - index2 := index2 – 1
- 如果 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]))