★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★Given an array A of integers, return true if and only if we can partition the array into three non-emptyparts 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:
Input: [0,2,1,-6,6,-7,9,1,2,0,1]Output: trueExplanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
Example 2:
Input: [0,2,1,-6,6,7,9,-1,2,0,1]Output: false
Example 3:
Input: [3,3,6,5,-2,2,5,1,-9,4]Output: trueExplanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
Note:
3 <= A.length <= 50000-10000 <= A[i] <= 10000
给定一个整数数组 A，只有我们可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果我们可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
示例 1：
输出：[0,2,1,-6,6,-7,9,1,2,0,1]输出：true解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
示例 2：
输入：[0,2,1,-6,6,7,9,-1,2,0,1]输出：false
示例 3：
输入：[3,3,6,5,-2,2,5,1,-9,4]输出：true解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
提示：
3 <= A.length <= 50000-10000 <= A[i] <= 10000
Runtime: 364 ms
Memory Usage: 19.5 MB
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 var sum:Int = 0 4 var n:Int = A.count 5 for i in 0.. 364ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 var total = 0 4 for i in 0.. 372ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 let count = A.count 4 var sum = 0 5 for item in A { 6 sum = sum + item 7 } 8 guard sum % 3 == 0 else { return false } 9 let part = Int(sum / 3)10 print(part)11 var i = -112 var j = count13 var part1 = 014 var part2 = 015 while i+1 j {27 return false28 }29 }30 31 var checkPart2 = true32 if checkPart2 {33 checkPart2 = false34 while part2 != part && i < j+1 {35 part2 = part2 + A[j]36 j = j - 137 }38 j = j + 139 if i+1 > j {40 return false41 }42 }43 44 if part1 == part2, part1 == part, i < j {45 return true46 }47 }48 return false49 }50 } 376ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 let aSum = A.reduce(0, +) 4 if aSum % 3 != 0 { 5 return false 6 } 7 let expectedSectionSum = aSum / 3 8 var expectedSectionSumSeenCount = 0 9 var currentSectionSum = 010 for i in 0.. 380ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 let sum = A.reduce(0, +) 4 guard sum % 3 == 0 else { return false } 5 let target = sum / 3 6 var split = [Int](), currSum = 0 7 for i in 0.. = 2 && 0 <= split[0] && split[0] < split[1] && split[1] < A.count15 }16 } 400ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 guard A.count >= 3 else { 4 return false 5 } 6 7 let sum = A.reduce(0) { $0 + $1 } 8 guard sum % 3 == 0 else { 9 return false10 }11 let partition = sum / 312 var count = 0 13 var current = 014 for a in A {15 current += a16 if current == partition {17 count += 118 current = 019 }20 }21 return count != 0 && count % 3 == 022 }23 } 408ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 var firstSum = 0 4 let total = A.reduce(0, +) 5 for (index, element) in A.enumerated() { 6 firstSum += element 7 let twoSums = total - firstSum 8 if twoSums % 2 == 0 { 9 if twoSums / 2 == firstSum && A.count - index > 2 {10 let subarray: [Int] = Array(A[index.. Bool {19 var leftover = a.reduce(0, +)20 for (index, element) in a.enumerated() {21 leftover -= element22 if leftover == sum && a.count - index > 1 {23 return true24 }25 }26 return false27 }28 } 420ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 guard A.count >= 3 else { return false } 4 5 var prefixSums = Array(repeating: 0, count: A.count + 1) 6 7 for (i, num) in A.enumerated() { 8 prefixSums[i + 1] = prefixSums[i] + num 9 }10 11 let sum = prefixSums.last!12 13 guard sum % 3 == 0 else { return false }14 15 let partitionSum = sum / 316 17 var a: Int?18 var b: Int?19 20 for (i, num) in prefixSums.enumerated() {21 if num == partitionSum && a == nil {22 a = i23 } else if num == (partitionSum * 2) && b == nil && a != nil {24 b = i25 return true26 }27 }28 29 return false30 }31 } 440ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 if A.count < 3 { 4 return false 5 } 6 if A.count == 3 { 7 return (A[0] == A[1]) && (A[0] == A[2]) && (A[1] == A[2]) 8 } 9 // start for the match.10 var first = false11 var second = false12 var third = false13 var firstSum = 014 var secondSum = 015 var thirdSum = 016 let totalSum = A.reduce(0,+)17 if (totalSum % 3) != 0 {18 return false19 }20 for number in A {21 firstSum += number22 if !first && (firstSum == (totalSum / 3)) {23 print("First met")24 first = true25 continue26 }27 if first && !second{28 secondSum += number29 if secondSum == (totalSum / 3) {30 print("Second met")31 second = true32 continue33 }34 }35 if second {36 thirdSum += number37 if thirdSum == (totalSum / 3) {38 print("Third met")39 }40 }41 }42 if thirdSum == (totalSum / 3) {43 return true44 }45 return false46 }47 } 452ms
1 class Solution { 2 func canThreePartsEqualSum(_ A: [Int]) -> Bool { 3 var prefix: [Int] = [0] 4 prefix.reserveCapacity(A.count + 1) 5 for a in A { 6 prefix.append(prefix.last! + a) 7 } 8 9 var first: Int?10 var second: Int?11 12 guard prefix.last! % 3 == 0 else {13 return false14 }15 16 let oneThird = prefix.last! / 317 for (i, p) in prefix.enumerated() {18 if p == oneThird {19 first = i20 break21 }22 }23 24 let twoThird = oneThird * 225 for (i, p) in prefix.enumerated().reversed() {26 if p == twoThird {27 second = i28 break29 }30 }31 32 if let first = first,33 let second = second {34 return first < second35 }36 37 return false38 }39 }