解題思路
題目要求數(shù)組能被分成和相等的三個部分菩掏，那么數(shù)組之和必然是3的倍數(shù)爽彤，如果不滿足這個先決條件网缝，則可以直接返回False。
在滿足數(shù)組和是3的倍數(shù)之后达吞，就從前往后遍歷數(shù)組，則每一個非空部分的和都應(yīng)當(dāng)是 sum(A) / 3荒典。因此我們需要找到索引 i 和 j 使得：
A[0] + A[1] + ... + A[i] = sum(A) / 3;
A[i + 1] + A[i + 2] + ... + A[j] = sum(A) / 3宗挥。這等價于 A[0] + A[1] + ... + A[j] = sum(A) / 3 * 2 且 j > i。
首先需要找出索引 i种蝶。具體地契耿，我們從第一個元素開始遍歷數(shù)組 A 并對數(shù)組中的數(shù)進行累加。當(dāng)累加的和等于 sum(A) / 3 時螃征，我們就將當(dāng)前的位置置為索引 i搪桂。
我們從 i + 1 開始繼續(xù)遍歷數(shù)組 A 并進行累加，當(dāng)累加的和等于 sum(A) / 3 * 2 時盯滚，我們就得到了索引 j踢械，可以返回 true 作為答案。如果我們無法找到索引 i 或索引 j魄藕，那么返回 false内列。
復(fù)雜度分析：
時間復(fù)雜度：O(N)，其中 N 是數(shù)組 A 的長度背率。我們最多只需要遍歷一遍數(shù)組就可以得到答案话瞧。
空間復(fù)雜度：O(1)嫩与。我們只需要使用額外的索引變量 i，j 以及一些存儲數(shù)組信息的變量交排。
代碼
class Solution:
def canThreePartsEqualSum(self, A: List[int]) -> bool:
s = sum(A)
if s%3 != 0:
return False
else:
r = int(s//3)
n = len(A)
i, cur = 0, 0
while i < n:
cur += A[i]
if cur == r:
break
i += 1
if cur != r:
return False
j = i+1
while j+1 < n: # 需要滿足最后一個數(shù)組非空
cur += A[j]
if cur == 2*r:
return True
j += 1
return False
