|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +Given an array A of integers, return true if and only if we can partition the |
| 4 | +array into three non-empty parts with equal sums. |
| 5 | +
|
| 6 | +Formally, we can partition the array if we can find indexes i+1 < j with (A[0] |
| 7 | ++ A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + |
| 8 | +A[A.length - 1]) |
| 9 | +
|
| 10 | +Example 1: |
| 11 | +
|
| 12 | +Input: [0,2,1,-6,6,-7,9,1,2,0,1] |
| 13 | +Output: true |
| 14 | +Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1 |
| 15 | +Example 2: |
| 16 | +
|
| 17 | +Input: [0,2,1,-6,6,7,9,-1,2,0,1] |
| 18 | +Output: false |
| 19 | +Example 3: |
| 20 | +
|
| 21 | +Input: [3,3,6,5,-2,2,5,1,-9,4] |
| 22 | +Output: true |
| 23 | +Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4 |
| 24 | +
|
| 25 | +Note: |
| 26 | +
|
| 27 | +3 <= A.length <= 50000 |
| 28 | +-10000 <= A[i] <= 10000 |
| 29 | +""" |
| 30 | +fromtypingimportList |
| 31 | + |
| 32 | + |
| 33 | +classSolution: |
| 34 | +defcanThreePartsEqualSum(self,A:List[int])->bool: |
| 35 | +s=sum(A) |
| 36 | +ifs%3!=0: |
| 37 | +returnFalse |
| 38 | + |
| 39 | +target=s//3 |
| 40 | +count=0 |
| 41 | +cur_sum=0 |
| 42 | +forainA: |
| 43 | +cur_sum+=a |
| 44 | +ifcur_sum==target: |
| 45 | +count+=1 |
| 46 | +cur_sum=0 |
| 47 | +# elif cur_sum > target: |
| 48 | +# return False |
| 49 | +# can have negative number |
| 50 | + |
| 51 | +returncount==3andcur_sum==0 |
| 52 | + |
| 53 | + |
| 54 | +if__name__=="__main__": |
| 55 | +assertSolution().canThreePartsEqualSum([3,3,6,5,-2,2,5,1,-9,4])==True |