【題目描述】
給定一個(gè)整數(shù)數(shù)組 A润文，只有我們可以將其劃分為三個(gè)和相等的非空部分時(shí)才返回 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]) 就可以將數(shù)組三等分宜雀。
【示例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
【思路】
1辐董、首先判斷數(shù)組元素和是否被3整除，不能被3整除直接返回false
2禀综、使用雙指針
3简烘、左右指針前后移動(dòng)，直到碰到A[0-left]定枷， A[right-length-1]的區(qū)間和 都等于ave平均值孤澎，返回true 否則返回false
4、時(shí)間復(fù)雜度O(n)
5欠窒、空間復(fù)雜度O(1)
Swift代碼實(shí)現(xiàn):
func canThreePartsEqualSum(_ A: [Int]) -> Bool {
if A.count < 3 { return false }
if A.count == 3 {
return A[0] == A[1] && A[0] == A[2]
}
var sum = 0
for n in A {
sum+=n
}
if sum%3 != 0 {
return false
}
let ave = sum/3 //平均值
var front = 0
var last = A.count-1
var tmpF = 0,tmpL = 0
while front < last {
if tmpF != ave {
tmpF+=A[front]
front+=1
}
if tmpL != ave {
tmpL+=A[last]
last-=1
}
if tmpF == ave && tmpL == ave {
return true
}
}
return false
}
