每日一题——LeetCode1013.将数组分成和相等的三个部分

方法一 个人方法：

既然和能被分成三部分，那么数组的和一定是3的倍数，所以先求和sum，如果sum不能整除3则直接返回false

按照题意，三个部分是按照数组原顺序分成的，那么从数组开头开始每一项求和，当和等于sum/3时代表已经找到第一组，将count重置为0继续寻找第二组，res记录满足和为sum/3的组数

当res===3的时候就代表刚好找到三组和为sum/3即满足题意，res>=3的条件是为了满足arr里元素都为0的特殊情况

var canThreePartsEqualSum = function(arr) {
    var sum = arr.reduce((a,b)=>a+b,0)
    var count=0,res=0
    if(sum%3!=0) return false
    for(var i=0;i<arr.length;i++){
        count+=arr[i]
        if(count===sum/3){
            count=0
            res++
        }
    }
    return res>=3
};

?消耗时间和内存情况：

方法二 动态规划：

维护一个数组res,res[i]=arr[0]+arr[1]+...+arr[i-1]+arr[i]，根据分析可得：

1、res[res.length-1]即为arr数组的和，它应该能被3整除，如果不能则返回false

2、假设分成三部分和都为n，那么res[res.length-1]===3n，且必然存在p,q，使得

0<p<q<res.length-2,且res[p]=n,res[q]=2n

var canThreePartsEqualSum = function(arr) {
    let res = [arr[0]];
    for (let i = 1; i < arr.length; i++) {
        res.push(res[i - 1] + arr[i]);
    }
    let single = res[res.length - 1] / 3;
    let part1 = res.indexOf(single);
    let part2 = res.indexOf(single * 2, part1 + 1);
    return part2 > part1 && part1 > -1 && part2 < res.length - 1;
};

消耗时间和内存情况：