描述
Given an array A
of integers, return true
if and only if we can partition the array into three non-empty parts with equal sums.
Formally, we can partition the array if we can find indexes i+1 < j
with (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])
Example 1:
1 2 3 Input: A = [0,2,1,-6,6,-7,9,1,2,0,1] Output: true Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
Example 2:
1 2 Input: A = [0,2,1,-6,6,7,9,-1,2,0,1] Output: false
Example 3:
1 2 3 Input: A = [3,3,6,5,-2,2,5,1,-9,4] Output: true Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
Constraints:
3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4
分析
水题。
解决方案1(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public boolean canThreePartsEqualSum (int [] A) { int sum = 0 ; for (int i = 0 ; i < A.length; i++) { sum += A[i]; } if (sum % 3 != 0 ) { return false ; } sum = sum / 3 ; int sumA = A[0 ], sumC = A[A.length-1 ]; int i = 1 , j = A.length-2 ; while (i < j) { if (sumA != sum) { sumA += A[i++]; } if (sumC != sum) { sumC += A[j--]; } if (sumA == sum && sumC == sum && i <= j) { return true ; } } return false ; } }
解决方案(Golang)
使用前缀和解决。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 func canThreePartsEqualSum(arr []int) bool { arrLen := len(arr) preSum := make([]int, arrLen) sufSum := make([]int, arrLen) preSum[0] = arr[0] for i := 1; i < arrLen; i++ { preSum[i] = preSum[i-1] + arr[i] } if preSum[arrLen-1] % 3 != 0 { return false } sufSum[arrLen-1] = arr[arrLen-1] for i := arrLen-2; i >= 0; i-- { sufSum[i] = sufSum[i+1] + arr[i] } for i := 0; i < arrLen; i++ { if preSum[i] * 3 != preSum[arrLen-1] { continue } for j := i+2; j < arrLen; j++ { if sufSum[j] == preSum[i] { return true } } } return false }