Partition Array Into Three Parts With Equal Sum
求一个数组能不能分为三个小数组,并且这三个小数组的和相等。我们已知目标是三个小数组,所以数组能被3整除。然后再找到小数组目标和是多少。计算是否有三个小数组的目标和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public boolean canThreePartsEqualSum(int[] A) { int sum = 0; for(int a : A) { sum += a ; // calculate sum } if(sum % 3 != 0) { return false; // divide by 3 ? } sum /= 3; // get the sum goal int count = 0; // count how many sum we have int tmp = 0; for(int a : A) { tmp += a; if(tmp == sum){ // if we find one count++; tmp = 0; } if(count == 3) // if there 3 return true; } return false; } } |