前言
本系列文章为《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
}
评论