这题有个坑,就是如果采用L->R 单向统计和为sum/3的子串时会存在:
A,B,C,D,E 5个子串和都为sum/3,看似是false,但是通过重新切分,可以变为
AB1, B2CD1, D2E 来组合成三个子串和为sum/3,见case71.
/*
* @lc app=leetcode id=1013 lang=cpp
*
* [1013] Partition Array Into Three Parts With Equal Sum
*/
// @lc code=start
class Solution {
public:
bool canThreePartsEqualSum(vector<int>& arr) {
int N = arr.size();
int sum = 0;
for(int i=0;i<N;i++) sum += arr[i];
if(sum % 3 != 0) return false;
sum /= 3;
int i = 0, j = N-1 , t;
t = 0;
for(;i<N;i++){
t += arr[i];
if(t == sum){
break;
}
}
t = 0;
for(;j>=0;j--){
t += arr[j];
if(t == sum){
break;
}
}
if(i+1>=j) return false;
t = 0;
for(int k=i+1;k<j;k++){
t += arr[k];
}
if(t == sum) return true;
return false;
}
};
// @lc code=end