题目概述
给定一个整数数组 arr，判断是否可以将其划分为三个和相等的非空部分。
示例
示例 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整除，那么无法分成三等分，直接返回 false。然后，使用双指针技巧，找到数组的两个分界点，使得每个分区的和都等于总和的1/3。
算法步骤
它接受一个整数数组 arr 作为输入，并返回一个布尔值，表示该数组是否可以被分成三个和相等的部分。 首先，函数计算了数组的前缀和 preSum 和后缀和 sufSum，然后检查整个数组的和是否能被 3 整除。如果可以，它进一步检查是否存在两个不重叠的子数组，它们的和相等，且这两个子数组将原数组分成了三个和相等的部分。 这个函数的时间复杂度是 O(N)，其中 N 是数组的长度。这是因为它只需要遍历数组一次来计算前缀和和后缀和，然后再遍历一次数组来查找满足条件的子数组。
算法实现
// 函数 canThreePartsEqualSum 用于判断一个整数数组是否可以被分成三个和相等的部分
func canThreePartsEqualSum(arr []int) bool {
// N 表示数组的长度
N := len(arr)
// preSum 是一个数组，用于存储从数组第一个元素到第 i 个元素的和
preSum := make([]int, N)
// 初始化 preSum 的第一个元素为数组的第一个元素
preSum[0] = arr[0]
// 计算 preSum 数组，preSum[i] 表示从数组第一个元素到第 i 个元素的和
for i := 1; i < N; i++ {
preSum[i] = preSum[i-1] + arr[i]
}
// 首先检查数组总和是否能被 3 整除，如果不能，则直接返回 false
if preSum[N-1]%3 != 0 {
return false
}
// sufSum 是一个数组，用于存储从数组最后一个元素到第 i 个元素的和
sufSum := make([]int, N)
// 初始化 sufSum 的最后一个元素为数组的最后一个元素
sufSum[N-1] = arr[N-1]
// 计算 sufSum 数组，sufSum[i] 表示从数组最后一个元素到第 i 个元素的和
for i := N - 2; i >= 0; i-- {
sufSum[i] = sufSum[i+1] + arr[i]
}
// 遍历数组，寻找是否存在两个索引 i 和 j（i < j），使得前 i 个元素的和等于后 j - i - 1 个元素的和
for i := 0; i < N; i++ {
// 如果前 i 个元素的和乘以 3 等于数组总和，则可以继续查找
if preSum[i]*3 != preSum[N-1] {
continue
}
// 从 i+2 到数组末尾遍历，查找是否存在一个索引 j，使得前 i 个元素的和等于后 j - i - 1 个元素的和
for j := i + 2; j < N; j++ {
// 如果找到这样的索引 j，则说明数组可以被分成三个和相等的部分，返回 true
if preSum[i] == sufSum[j] {
return true
}
}
}
// 如果遍历结束后没有找到符合条件的 i 和 j，则返回 false
return false
}
js暴力解
/**
* @param {number[]} arr
* @return {boolean}
*/
var canThreePartsEqualSum = function(arr) {
let sum = arr.reduce((a,b) => a + b)
let num = 3
let temp = 0
for(let a of arr){
temp += a
if (temp === sum / 3) num--, temp = 0
}
return num <= 0
};