[Swift]LeetCode1013. 將數組分成和相等的三個部分 | Partition Array Into Three Parts With Equal Sum...

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：?https://www.cnblogs.com/strengthen/p/10587854.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強烈建議點擊原文地址閱讀！支持作者！支持原創！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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: true
Explanation: 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: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Note:

1. 3 <= A.length <= 50000
2. -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

提示：

1. 3 <= A.length <= 50000
2. -10000 <= A[i] <= 10000

---

Runtime:?364 ms

Memory Usage:?19.5 MB

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        var sum:Int = 0
        var n:Int = A.count
        for i in 0..<n {sum += A[i]}
        if sum % 3 != 0 {return false}
        sum /= 3
        var cnt:Int = 0
        var ok:Int = 0
        for i in 0..<n
        {
            cnt += A[i]
            if sum == cnt && ok != 2
            {
                cnt = 0
                ok += 1
            }
        }
        return ok == 2 && sum == cnt        
    }
}

---

364ms

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        var total = 0
        for i in 0..<A.count {
            total = total + A[i]
        }
        
        let target = total / 3
        if total % 3 != 0 {
            return false
        }
        
        var sum = 0
        var count = 0
        for i in 0..<A.count {
            sum = sum + A[i]
            if sum == target {
                count = count + 1
                sum = 0
                continue
            }
        }

        if count == 3 && sum == 0 {
            return true
        }
        
        return false
    }
}

---

372ms

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        let count = A.count
        var sum = 0
        for item in A {
            sum = sum + item
        }
        guard sum % 3 == 0 else { return false }
        let part = Int(sum / 3)
        print(part)
        var i = -1
        var j = count
        var part1 = 0
        var part2 = 0
        while i+1<j {
            i = i + 1
            j = j - 1
            var checkPart1 = true
            if checkPart1 {
                checkPart1 = false
                while part1 != part && i < j+1 {
                    part1 = part1 + A[i]
                    i = i + 1
                }
                i = i - 1
                if i+1 > j {
                    return false
                }
            }
            
            var checkPart2 = true
            if checkPart2 {
                checkPart2 = false
                while part2 != part && i < j+1 {
                    part2 = part2 + A[j]
                    j = j - 1
                }
                j = j + 1
                if i+1 > j {
                    return false
                }
            }

            if part1 == part2, part1 == part, i < j {
                return true
            }
        }
        return false
    }
}

---

376ms

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        let aSum = A.reduce(0, +)
        if aSum % 3 != 0 {
            return false
        }
        let expectedSectionSum = aSum / 3
        var expectedSectionSumSeenCount = 0
        var currentSectionSum = 0
        for i in 0..<A.count {
            let value = A[i]
            if value == 0 {
                continue
            }
            currentSectionSum += value
            if currentSectionSum == expectedSectionSum {
                expectedSectionSumSeenCount += 1
                currentSectionSum = 0
            }
        }
        return expectedSectionSumSeenCount == 3
    }
}

---

380ms

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        let sum = A.reduce(0, +)
        guard sum % 3 == 0 else { return false }
        let target = sum / 3
        var split = [Int](), currSum = 0
        for i in 0..<A.count {
            currSum += A[i]
            if currSum == target {
                split.append(i)
                currSum = 0
            }
        }
        return split.count >= 2 && 0 <= split[0] && split[0] < split[1] && split[1] < A.count
    }
}

---

400ms

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        guard A.count >= 3 else {
            return false
        }
        
        let sum = A.reduce(0) { $0 + $1 }
        guard sum % 3 == 0 else {
            return false
        }
        let partition = sum / 3
        var count = 0 
        var current = 0
        for a in A {
            current += a
            if current == partition {
                count += 1
                current = 0
            }
        }
        return count != 0 && count % 3 == 0
    }
}

---

408ms

class Solution {  
  func canThreePartsEqualSum(_ A: [Int]) -> Bool {
    var firstSum = 0
    let total = A.reduce(0, +)
    for (index, element) in A.enumerated() {
      firstSum += element
      let twoSums = total - firstSum
      if twoSums % 2 == 0 {
        if twoSums / 2 == firstSum && A.count - index > 2 {
          let subarray: [Int] = Array(A[index..<A.count])
          return validateSecondPart(subarray, withSum: firstSum)
        }
      }
    }
    return false
  }
  
  func validateSecondPart(_ a: [Int], withSum sum: Int) -> Bool {
    var leftover = a.reduce(0, +)
    for (index, element) in a.enumerated() {
      leftover -= element
      if leftover == sum && a.count - index > 1 {
        return true
      }
    }
    return false
  }
}

---

420ms

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        guard A.count >= 3 else { return false }

        var prefixSums = Array(repeating: 0, count: A.count + 1)

        for (i, num) in A.enumerated() {
            prefixSums[i + 1] = prefixSums[i] + num
        }

        let sum = prefixSums.last!

        guard sum % 3 == 0 else { return false }

        let partitionSum = sum / 3

        var a: Int?
        var b: Int?

        for (i, num) in prefixSums.enumerated() {
            if num == partitionSum && a == nil {
                a = i
            } else if num == (partitionSum * 2) && b == nil && a != nil {
                b = i
                return true
            }
        }

        return false
    }
}

---

440ms

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        if A.count < 3 {
            return false
        }
        if A.count == 3 {
            return (A[0] == A[1]) && (A[0] == A[2]) && (A[1] == A[2])
        }
        // start for the match.
        var first = false
        var second = false
        var third = false
        var firstSum = 0
        var secondSum = 0
        var thirdSum = 0
        let totalSum = A.reduce(0,+)
        if (totalSum % 3) != 0 {
            return false
        }
        for number in A {
            firstSum += number
            if !first && (firstSum == (totalSum / 3)) {
                print("First met")
                first = true
                continue
            }
            if first && !second{
                    secondSum += number
                    if secondSum == (totalSum / 3) {
                        print("Second met")
                        second = true
                        continue
                    }
            }
            if second {
                thirdSum += number
                    if thirdSum == (totalSum / 3) {
                        print("Third met")
                    }
            }
        }
        if thirdSum == (totalSum / 3) {
            return true
        }
        return false
    }
}

---

452ms

class Solution {
    func canThreePartsEqualSum(_ A: [Int]) -> Bool {
        var prefix: [Int] = [0]
        prefix.reserveCapacity(A.count + 1)
        for a in A {
            prefix.append(prefix.last! + a)
        }
        
        var first: Int?
        var second: Int?
        
        guard prefix.last! % 3 == 0 else {
            return false
        }
        
        let oneThird = prefix.last! / 3
        for (i, p) in prefix.enumerated() {
            if p == oneThird {
                first = i
                break
            }
        }
        
        let twoThird = oneThird * 2
        for (i, p) in prefix.enumerated().reversed() {
             if p == twoThird {
                second = i
                break
            }
        }
        
        if let first = first,
            let second = second {
                return first < second
        }
        
        return false
    }
}

?