“This is the 24th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The original link

1013. Divide an array into three equal and equal parts – LeetCode (leetcode-cn.com)

Topic describes

Given an integer array arr, return true only if it can be divided into three non-empty parts equal to each other, and false otherwise.

Formally, if we can find the index I + 1 < j and satisfy (arr[0] + arr[1] +… + arr[i] == arr[i + 1] + arr[i + 2] + … + arr[j – 1] == arr[j] + arr[j + 1] + … + arr[arr.length-1]) to divide the array into three equal parts.

The test case

Example 1:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1] Output: true Explanation: 0 + 2 + 1 = -6 + 6-7 + 9 + 1 = 2 + 0 + 1Copy the code

Example 2:

Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1Copy the code

Parameter limits

  • 3 <= arr.length <= 5 * 104
  • -104 <= arr[i] <= 104

Analysis of the

At first glance, I think we need to use greedy to divide the array elements into 3 pieces, to ensure that the sum of each piece of data is equal. But after careful reading, it is actually two cuts directly on the original array, we just need to locate the two cuts, and whether the array can be obtained in this way to get three and equal parts

Note that we need to ensure that each subarray contains at least one element!

We need to figure out the sum of the arrays, and then get the sum of each of the subarrays

In the case that the array can be split into three parts, we just need to find the boundary between the sum of the first two parts. If we find two boundaries, and the last array has elements, we can return true; In all other cases, return false

code

var canThreePartsEqualSum = function(arr) {
    let sum = arr.reduce((a, b) = > a + b, 0);
    if (sum % 3! =0) return false;
    let avg = sum / 3;
    let n = 2;
    // Start from the beginning, find I, j
    let count = 0;
    for (let i = 0; i < arr.length - 1; i++) {
        count += arr[i];
        if (count == avg) {
            n--;
            count = 0;
        }
        if (n == 0) {
            break; }}return n == 0;
};
Copy the code

Today’s force buckle brush problem share here, thank you for reading ~