1013-贪心:将数组分成和相等的三部分

题目地址

解题思路

题目：
给你一个整数数组 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]) 就可以将数组三等分。

只要找到对应的i和j,就能满足条件。可以使用双指针将数据分为三部分,求出三部分的和，如果left = middle = right，那么返回true；如果不满足条件，移动双指针。

此事有几种情况需要讨论：
1.如果left <= right :
a.如果middle > right ，说明middle的值是最大的，left值最小，那么i ++ ，增加left的值;
b. 如果middle < left，说明left的值是最小的，right值最大，那么j—，增加中间的值；
c. 如果left < middle < right，说明left最小，right最大，那么i++ ，j—，增大两边的值；

2.如果left > right ：
a.如果middle > left ，说明middle的值是最大的，right值最小，那么j— ，增加右侧的值;
b. 如果middle < right，说明right的值是最小的，left值最大，那么i++，增加中侧的值；
c. 如果right < middle < left，说明left最小，right最大，那么j—，增大两边的值；

代码

const sumFn = (arr,start,end)=>{
    let res = 0;
   for(let i = start;i<=end;i++){
      res += arr[i]
   }
   return res;
}
var canThreePartsEqualSum = function(arr) {
    const len = arr.length;
    let i = 0,j = len - 1;
    while(i+1 < j && j <= len - 1){
        let left = sumFn(arr,0,i);
        let middle = sumFn(arr,i+1,j-1);
        let right = sumFn(arr,j,len - 1);
        if(left == middle  && middle == right){
            return true;
         }else if(left <= right){
             if(middle > right){
                i++;
             }else if(middle < left){
                 j--;
             }else {
               i++;
               j--;
             }
         }else if(left > right){
            if(middle > left){
                j--;
             }else if(middle < right){
                 i++;
             }else {
               j--;
             }
         }
    }
    return false;
};

以上解法，效率太低。根据题解，做了以下的思考：

优化

优化后的思路：

1.求全部的和sum，相等的三部分，那么，和一定要能被3整除，如果不可以就返回false
2.对于

(arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

也就是

arr[0] + arr[1] + ...arr[i] = sum / 3

 arr[i+1]+arr[i+2] + ...+arr[j] = sum /3

arr[0]+ arr[1] + ...+arr[j] = sum / 3 * 2

如果能找到合适的i，j，就返回true,否则返回false

代码

var canThreePartsEqualSum2 = (arr)=>{
    const len = arr.length;
    let sum = 0;
    sum = arr.reduce((pre,cur)=>{ return pre + cur},0)
    if(sum % 3 !==0) return false;

    const target = sum / 3;
    let i = 0,curSum = 0;

    while(i<len){
       curSum += arr[i];
       if(curSum == target){
          break;
       }
       ++i;
    }

    if(curSum != target) return false;
    let j = i+1;
    while(j+1<len){
       curSum += arr[j];
       if(curSum === target * 2){
           return true;
       }
       ++j
    }
    return false;
}