Divide the array into three equal parts [problem analysis]

Preface

Solve more than one problem , Open your eyes , See following , Achieve mastery through a comprehensive .

One 、 Divide the array into three parts equal to and

Two 、 Multiple solutions to problems

1、 branch 3 Group

//  Divide the array into three parts equal to and .
public class CanThreePartsEqualSum {
    
    /* target: Divided into three ordered subarrays , Require three subarrays and equal .  The sum of three ordered subarrays is equal , That means every array and  = sum / 3.  When sum % 3 != 0 when , It is impossible to divide into three equal ordered subarrays , After all, numbers can't be taken apart .  Then iterate through the array , Find the sum of successive subarrays as  sum / 3 Of , After traversing , If you can find three , Group successfully . */
    public boolean canThreePartsEqualSum(int[] arr) {
    
        //  Get array and .
        //  This tone API The way is too slow .
        // int total = Arrays.stream(arr).sum();
        int total = 0;
        for (int i : arr) total += i;
        //  Decide whether it is right 3 Remainder .
        if (total % 3 != 0) return false;
        //  Get the sum of each group .
        int target = total / 3;
        //  Traverse arr, Find out how many groups can be divided into target
        int n = 0, cur = 0;
        for (int i : arr) {
    
            if ((cur += i) == target && (++n) == n) cur = 0;
            //  according to bug1/2 modify .
            if (n >= 3) return true;
        }
        //  Divide into three groups and you will succeed , Otherwise failure .
        // bug1: It may all be 0.
        // return n == 3;
        // bug2: There are many pairs and for 0 Of .
        // return n == 3 || n == arr.length;
        // return n >= 3;
        return false;
    }

}

2、 branch 2 Group

//  Complete the traversal from left to right , There will be details ---- There is 0 To whom ？ So using n >= 3 To determine .
//  How to calculate from both ends at the same time , And only calculate 2 Group , Then the remaining group in the middle must be target, Can solve 0 Who belongs to -- All belong to the middle .
class CanThreePartsEqualSum2 {
    
    /* target: Divided into three ordered subarrays , Require three subarrays and equal .  The sum of three ordered subarrays is equal , That means every array and  = sum / 3.  When sum % 3 != 0 when , It is impossible to divide into three equal ordered subarrays , After all, numbers can't be taken apart .  Then double pointer traverses the array , Find the sum of successive subarrays before and after  sum / 3 Of , Find two elements in between , The success is divided into three groups . */
    public boolean canThreePartsEqualSum(int[] arr) {
    
        //  Get array and .
        int total = 0;
        for (int i : arr) total += i;
        //  Decide whether it is right 3 Remainder .
        if (total % 3 != 0) return false;
        //  Get the sum of each group .
        int target = total / 3;
        //  Double pointer traverses the array back and forth , Find three groups of left, middle and right target
        int left = 1, right = arr.length - 2;
        int leftSum = arr[0], rightSum = arr[arr.length - 1];
        while (left < right) {
    
            if (leftSum != target) leftSum += arr[left++];
            if (rightSum != target) rightSum += arr[right--];
            if (leftSum == rightSum && rightSum == target && left <= right) return true;
        }
        return false;
    }
}

summary

1） Solve more than one problem , Open your eyes , See following .

reference

[1] LeetCode Divide the array into three parts equal to and