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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告