社区首页 >专栏 >LeetCode1013：将数组分成和相等的三个部分

LeetCode1013：将数组分成和相等的三个部分

机智的程序员小熊

发布于 2020-03-25 03:28:52

1.8K00

代码可运行

文章被收录于专栏：技术面面观技术面面观

运行总次数：0

代码可运行

前言

本系列文章为《leetcode》刷题笔记。

题目位置：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum/

项目位置：我的Github项目 https://github.com/pzqu/LeetCode

题目

给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引i+1 < j且满足(A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])就可以将数组三等分。

示例 1：

输出：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2：

输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

示例 3：

输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

提示：

3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4

思路

题目要点：

原数组砍成三段，每段是连续的
每段的和相等
总和/3就是每段的和

方法一：暴力破解

最直观的想法就暴力破解，要把一个线段砍成三段，那必然有两条分隔线，所以有两个循环来改变分隔线的位置。

第一个分隔线由i表示，切分开第一段和第二段，从0开始，最多到len(A)-2，因为后面两段至少要有一个值。区间为[0,i]

第二个分隔线由j表示，切开第二段和第三段，从1开始，给第一段至少一个值，给第最后一段，至少一个值。区间为[i+1,j]，最后一个区间为[j+1,len(A)-1]

 for i := 0; i < len(A)-2; i++ {
        ....
        for j := i + 1; j < len(A)-1; j++ {

这样三段的和为suma,sumb,sumc ，起始值为0。

为了减少循环次数，不要每次改变长度都重新加一次sumc，只要先统计一次第三段的和赋值给tmpsumc留给后面用，每次增加第一段长度就给第二段长度清零，第三段总和等于 tmpsumc

每次前两段长度增加的时候，sumc剪去j新包含的数即可，如下第二层循环：

for j := i + 1; j < len(A)-1; j++ {
            sumb = sumb + A[j]
            sumc = sumc - A[j]
            ......

每次第二段长度增加1、第三段长度减少1，都要进行一次判断是否三个和相等。

如果第二段和第三段各自的和都和第一段不相等，那就先将第三段总和tmpsumc - A[i+1]，让第一段长度加1，第二段长度清零

但是速度很慢：

方法二：数学

这真的是一个数学题，如果已知总和，由于三段长度相等，只要找到前两段，那第三段一定相等。

所以有如下代码统计总和

for i := 0; i < len(A); i++ {
        sum = sum + A[i]
    }

如果被3除不尽则失败

sum%3 != 0

找出前两段，count是统计次数

for i := 0; i < len(A); i++ {
        tmpSum = tmpSum + A[i]
        if tmpSum == singeSum {
            count = count + 1
            tmpSum = 0
            if count == 2 && i < len(A)-1 {
                return true
            }
        }
    }

其中count == 2 && i < len(A)-1是保证第三段至少有一个数

ps: 有人会问了，因为数组有正有负，如果我找到了更长的第一段怎么办？

第二段的位置总是在第一段后面的，第一段再长，都是小于第二段的长度的，总和我们都求出来了，只要找到第一段就好啦。

但如果你选择了更大的下标（不妨叫做 i1），可能就没有对应的满足要求的 j 了，所以选最小的是最安全的。只要第一段找到了，后面两段的和必然是sum/3 * 2,找得到就是，找不到就没了。

代码

方法一：暴力破解

func canThreePartsEqualSum(A []int) bool {
    suma, sumb, sumc := 0, 0, 0
    tmpsumc := 0

    for k := 1; k < len(A); k++ {
        tmpsumc = tmpsumc + A[k]
    }

    for i := 0; i < len(A)-2; i++ {
        suma = suma + A[i]
        sumb = 0
        sumc = tmpsumc
        for j := i + 1; j < len(A)-1; j++ {
            sumb = sumb + A[j]
            sumc = sumc - A[j]
            if suma == sumb && sumb == sumc {
                return true
            }
        }

        tmpsumc = tmpsumc - A[i+1]
    }
    return false
}

方法二：数学 Go

func canThreePartsEqualSum(A []int) bool {
    tmpSum, sum, singeSum, count := 0, 0, 0, 0

    for i := 0; i < len(A); i++ {
        sum = sum + A[i]
    }
    if sum%3 != 0 {
        return false
    }
    singeSum = sum / 3

    for i := 0; i < len(A); i++ {
        tmpSum = tmpSum + A[i]
        if tmpSum == singeSum {
            count = count + 1
            tmpSum = 0
            if count == 2 && i < len(A)-1 {
                return true
            }
        }
    }
    return false
}