Python 中将数组分成三个和相等的子数组

假设我们有一个整数数组 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
  • 当 index1 < index2 时
    • 当 index1 < index2 且 sum_left[index1] != required_sum 时
      • index1 := index1 + 1
    • 当 index2 > index1 且 sum_right[index2] != required_sum 时
      • index2 := index2 – 1
    • 如果 index1 < index2 且 index1 != index2，则返回真，否则返回假。

示例

让我们看看以下实现以更好地理解：

 在线演示

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

更新于: 2020年4月28日

352 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告