将数组分成和相等的三个部分[问题分析]

前言

一题多解，打开视野，见招拆招，融会贯通。

一、将数组分成和相等的三个部分

二、问题多解

1、分3组

// 将数组分成和相等的三个部分。
public class CanThreePartsEqualSum {
    
    /* target:分成三个有序子数组，要求三个子数组和相等。 三个有序子数组和相等，就意味着每个数组和 = sum / 3. 当sum % 3 != 0时，就不可能分成三个相等的有序子数组，毕竟数字不能拆开。 然后遍历数组，寻找连续子数组的和为 sum / 3的，遍历完后，如果能寻找到三个，则成功分组。 */
    public boolean canThreePartsEqualSum(int[] arr) {
    
        // 获取数组和。
        // 这种调API的方式太慢。
        // int total = Arrays.stream(arr).sum();
        int total = 0;
        for (int i : arr) total += i;
        // 判定能否对3取余。
        if (total % 3 != 0) return false;
        // 得到每组的和。
        int target = total / 3;
        // 遍历arr，寻找能分成多少组和为target
        int n = 0, cur = 0;
        for (int i : arr) {
    
            if ((cur += i) == target && (++n) == n) cur = 0;
            // 根据bug1/2修改.
            if (n >= 3) return true;
        }
        // 分成三组就成功，否则失败。
        // bug1:有可能全部为0.
        // return n == 3;
        // bug2:有很多对和为0的。
        // return n == 3 || n == arr.length;
        // return n >= 3;
        return false;
    }

}

2、分2组

// 按照从左到右遍历完，会有细节问题----存在0归属谁？所以采用n >= 3来判定。
// 如何从两头同时计算，且只计算2组，那么剩下中间一组必为target,可以解决0归属谁的问题--全部归属中间。
class CanThreePartsEqualSum2 {
    
    /* target:分成三个有序子数组，要求三个子数组和相等。 三个有序子数组和相等，就意味着每个数组和 = sum / 3. 当sum % 3 != 0时，就不可能分成三个相等的有序子数组，毕竟数字不能拆开。 然后双指针遍历数组，寻找前后连续子数组的和为 sum / 3的，寻找到两个且中间还有元素，则成功分三组。 */
    public boolean canThreePartsEqualSum(int[] arr) {
    
        // 获取数组和。
        int total = 0;
        for (int i : arr) total += i;
        // 判定能否对3取余。
        if (total % 3 != 0) return false;
        // 得到每组的和。
        int target = total / 3;
        // 双指针前后遍历数组，寻找左中右三组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;
    }
}

总结

1）一题多解，打开视野，见招拆招。

参考文献

[1] LeetCode 将数组分成和相等的三个部分