สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็ม เอาต์พุตของเราจะเป็นจริงก็ต่อเมื่อเราแบ่งอาร์เรย์ออกเป็นสามส่วนที่ไม่ว่างเปล่าซึ่งมีผลรวมเท่ากัน
อย่างเป็นทางการ เราสามารถแบ่งอาร์เรย์อาร์เรย์ถ้าเราสามารถหาดัชนี i+1
ดังนั้นหากอินพุตเป็น [0,2,1,-6,6,-7,9,1,2,0,1] ผลลัพธ์จะเป็นจริง สามอาร์เรย์จะเป็น [0,2,1], [-6,6,-7,9,1] และ [2,0,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
