Given an array A of integers, return true if and only if we can partition the array into three non-empty parts 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:
3 <= A.length <= 50000
-10000 <= A[i] <= 10000
1.思考
- 一开始想到的是直接暴力搜索用二重for循环找出i和j的位置，方法是可行的，但是时间复杂度太高，不能通过测试；
- 然后开始观察该题的特点，发现这其实就相当于把这组数分成三段：0~i, i+1~j, j+1~len-1，每一段的总和相等；
- 再进一步化简就可知：0~j的总和是0~i总和的2倍，0~len-1的总和是0~i总和的3倍；
- 那么先用n步计算出0到当前位置的总和，然后找到符合这样1倍、2倍、3倍关系的数即可；
- 看完题目不要太匆忙地做题，稍微分析一下题目就可以简化解决方案！
2.实现
class Solution {
public:
bool canThreePartsEqualSum(vector<int>& A) {
int len = A.size();
vector<int> sum;
int s1, s2, s3;
int s0 = 0;
for(int i=0; i<len; i++){
s0 += A[i];
sum.push_back(s0);//Sum of A[0] to A[i]
}
//sum[i]
//sum[j] = 2*summ[i]
//sum[len-1] = 3*summ[i]
for(int i=0; i<len-2; i++){
s1 = sum[i];
if(sum[len-1]==3*s1){//The sum of all must be 3 times of s1.
s2 = 2*s1;
s3 = 3*s1;
for(int j=i+1; j<len-1; j++){
if(sum[j]==s2 && sum[len-1]==s3){
return true;
}
}
}
}
return false;
}
};