给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 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]) 就可以将数组三等分。
示例 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
提示：
3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4
解题思想：
第一点：数组总和不为3的倍数的话，直接返回false；
- 理由如下：首先要能够分成三部分，其次三个部分的和要相等，然后数组元素总的和就是3倍的每一部分的总和，所以可以先直接用这个思想来解决返回false的情况
第二点：我们可以利用指针，用一个left和right指针分别从数组的左右两端开始遍历，当left循环遍历过的元素总和 = right循环遍历的元素总和的时候 = 数组所有元素总和的三分之一的时候，那么中间部分的总和必然也为 数组所有元素总和的三分之一
- 在这个过程中要注意的一点就是：循环体结束的条件是left < right - 1而不是 left < right
因为·left < right 可能会将数组分成两部分，违反了题目意思，比如 [2 -1 3 -2]
public boolean canThreePartsEqualSum(int[] A) { int sum = 0; for (int i : A) { sum += i; } if (sum % 3 != 0) { // 总和不是3的倍数，直接返回false return false; } // 先初始化双指针，使用双指针，从数组两头开始一起找，节约时间 int left = 0; int leftSum = A[left]; int right = A.length - 1; int rightSum = A[right]; // 使用left+1<right的援用，防止只能将数组分成两部分 // 例如：[1,-1,1,-1]，使用left < right作为判断条件就会出错 while (left + 1 < right) { if (leftSum == sum / 3 && rightSum == sum / 3) { // 左右两边都等于sum/3，中间也一定等于 return true; } if (leftSum != sum / 3) { // left = 0赋予了初值，应该先left++，在leftSum += A[left]; leftSum += A[++left]; } if (rightSum != sum / 3) { // right = 0赋予了初值，应该先right--，在rightSum += A[right]; rightSum += A[--right]; } } return false; }
这种的效率比较高
还有一种比较直观容易想到的，但是效率没有上述那么好的如下：
这种的解题思想第一步和上述方法一样，但是第二步的时候就是暴力循环，当累加的和 等于所有元素总和的三分之一之后然后记录下此时这个值在数组中的位置，并从此位置重新开始累加求和运算，依次遍历完整个数组。
public boolean canThreePartsEqualSum1(int[] A) { int sum = 0; for (int i : A) { sum += i; } if (sum % 3 != 0) { return false; } int s = 0; int flag = 0; for (int i : A) { s += i; if (s == sum / 3) { flag++; s = 0; } } // flag不一定等于3，例如[1,-1,1,-1,1,-1,1,-1] return flag >= 3; }
这种的运行截图如下：
