Python에서 동일한 합을 사용하여 배열을 세 부분으로 분할

정수 배열 A가 있다고 가정하고 배열을 합이 동일한 비어 있지 않은 세 부분으로 분할할 수 있는 경우에만 출력이 참이 됩니다.

공식적으로 (A[0] + A[1] + ... + A[i] is same as A[i+1] + A[ i+2] + ... + A[j-1] 및 A[j] + A[j-1] + ... + A[A.길이 - 1])

따라서 입력이 [0,2,1,-6,6,-7,9,1,2,0,1]이면 출력은 true가 됩니다. 세 개의 배열은 [0,2,1], [-6,6,-7,9,1] 및 [2,0,1]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• temp :=모든 요소의 합계, required_sum :=temp / 3
• 왼쪽에서 오른쪽으로 누적 합계를 저장하도록 sum_left 설정
• 오른쪽에서 왼쪽으로 누적 합계를 저장하도록 sum_right 설정
• index1 :=0 및 index2 :=배열 길이 – 1
• 인덱스1 <인덱스2:
  • index1 동안
  • 인덱스1 :=인덱스1 + 1
• 동안 index2> index1 및 sum_right[index2] !=required_sum
  • 인덱스2 :=인덱스2 – 1
• index1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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