LeetCode_前缀和_简单_1013.将数组分成和相等的三个部分

梦里梦外; 2023-10-07 19:53 46阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 arr，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i + 1 < j 且满足 (arr\[0\] + arr\[1\] + … + arr\[i\] == arr\[i + 1\] + arr\[i + 2\] + … + arr\[j - 1\] == arr\[j\] + arr\[j + 1\] + … + arr\[arr.length - 1\]) 就可以将数组三等分。

**示例 1：**  
输入：arr = \[0,2,1,-6,6,-7,9,1,2,0,1\]  
输出：true  
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

**示例 2：**  
输入：arr = \[0,2,1,-6,6,7,9,-1,2,0,1\]  
输出：false

**示例 3：**  
输入：arr = \[3,3,6,5,-2,2,5,1,-9,4\]  
输出：true  
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

**提示：**  
3 <= arr.length <= 5 \* 104  
\-104 <= arr\[i\] <= 104

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/partition-array-into-three-parts-with-equal-sum

## 2.思路 ##

（1）前缀和  
本题可以使用前缀和的思想，具体步骤如下：  
① 设 sum 为数组 arr 的所有元素之和，显然**如果 sum % 3 != 0，那么不能将数组 arr 三等分，直接返回 false 即可**；如果 sum % 3 == 0，则需要继续往下判断。

② 假设数组 arr 可以被三等分，即存在索引 i + 1 < j，使得 arr\[0…i\]、arr\[i + 1…j - 1\]、arr\[j…arr.length - 1\] 元素和相等（反推也成立）；

③ 如果再结合前缀和的知识，我们**设 arr\[0…i\]、arr\[0…j - 1\]、arr\[0…arr.length - 1\] 的和分别为 sum1、sum2、sum3**，那么在上面的三部分和相等的情况下，可以推出 `sum1 = sum2 - sum1 = sum3 - sum2（或者 sum1 = sum3 / 3、sum2 = sum1 * 2）`，并且该结论反推也成立。

④ 所以在求出 sum 后，我们只需再将数组 arr 的元素逐步累加（用变量 partSum 来记录），如果在累加的过程中出现了 partSum == sum1、partSum == sum2 的情况（注意顺序以及边界条件判断），那么说明数组 arr 可以被三等分；否则则不能。

相似题目：[LeetCode\_回溯\_中等\_698.划分为k个相等的子集][LeetCode_698._k]

## 3.代码实现（Java） ##

//思路1————前缀和
    class Solution {
        
        public boolean canThreePartsEqualSum(int[] arr) {
        
            int length = arr.length;
            int sum = 0;
            for (int num : arr) {
        
                sum += num;
            }
            if (sum % 3 != 0) {
        
                return false;
            }
            int partSum = 0;
            int divide = sum / 3;
            int cnt1 = 0;
            int cnt2 = 0;
            for (int i = 0; i < length; i++) {
        
                partSum += arr[i];
                if (cnt1 == 0 && partSum == divide) {
        
                    cnt1++;
                    //为了防止 divide == divide * 2 == sum == 0 的情况出现
                    continue;
                }
                /*
    				(1) cnt1 != 0: 控制 partSum == divide 和 partSum == divide * 2 出现的先后顺序
    				(2) i != length - 1: 边界情况判断，如果 sum == 0，那么 divide == divide * 2 == sum，
    					此时需要保证划分的三个部分均不为空
    			*/
                if (partSum == divide * 2 && cnt1 != 0 && i != length - 1) {
        
                    cnt2++;
                }
            }
            return cnt1 != 0 && cnt2 != 0;
        }
    }

[LeetCode_698._k]: https://blog.csdn.net/weixin_43004044/article/details/123589576