Mảng phân vùng thành ba phần với tổng bằng nhau trong Python

Giả sử chúng ta có một mảng A gồm các số nguyên, kết quả của chúng ta sẽ là true nếu và chỉ khi chúng ta có thể phân chia mảng thành ba phần không rỗng có tổng bằng nhau.

Về mặt hình thức, chúng ta có thể phân vùng mảng nếu chúng ta có thể tìm thấy các chỉ mục i + 1

Vì vậy, nếu đầu vào là [0,2,1, -6,6, -7,9,1,2,0,1], thì đầu ra sẽ là true. Ba mảng sẽ là [0,2,1], [-6,6, -7,9,1] và [2,0,1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• temp:=tổng của tất cả các phần tử và Requi_sum:=temp / 3
• đặt sum_left để lưu trữ tổng tích lũy từ trái sang phải
• đặt sum_right để lưu trữ tổng tích lũy từ phải sang trái
• index1:=0 và index2:=độ dài của mảng - 1
• while index1
• while index1
• index1:=index1 + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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]))

Đầu vào

[0,2,1,-6,6,-7,9,1,2,0,1]

Đầu ra

true