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

2020年3月12日 评论 108 views 2057字阅读6分51秒

前言

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

题目位置:力扣中国

项目位置:我的Github项目

题目

给你一个整数数组 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

思路

题目要点:
1. 原数组砍成三段,每段是连续的
2. 每段的和相等
3. 总和/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,找得到就是,找不到就没了。

代码

方法一:暴力破解

Go

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
}
weinxin
微信公众号
三分钟学习晦涩难懂的技术,分享开发、运维、云技术等方面知识,带您轻松打破技术壁垒,编程如鱼得水。欢迎您的关注~!
好烂啊有点差凑合看看还不错很精彩 (还没有人打分)
Loading...
小熊
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: