2021-08-28：给定一个正数数组arr，长度一定大于6（>=7），一定要选3个数字做分割点，从而分出4个部分，并且每部分都有数，分割点的数字直接删除，不属于任何4个部分中的任何一个。 返回有没有可能分出的4个部分累加和一样大，如：{3,2,3,7,4,4,3,1,1,6,7,1,5,2}，可以分成{3,2,3}、{4,4}、{1,1,6}、{1,5,2}。分割点是不算的！
福大大 答案2021-08-28：
前缀和存map。i位置作为第1刀。
时间复杂度：O(N)。
空间复杂度：O(N)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
arr := []int{1, 2, 1, 2, 1, 2, 1}
ret := canSplits2(arr)
fmt.Println(ret)
}
func canSplits2(arr []int) bool {
if len(arr) < 7 {
return false
}
// key 某一个累加和， value出现的位置
map0 := make(map[int]int)
sum := arr[0]
for i := 1; i < len(arr); i {
map0[sum] = i
sum = arr[i]
}
lsum := arr[0] // 第一刀左侧的累加和
for s1 := 1; s1 < len(arr)-5; s1 { // s1是第一刀的位置
checkSum := lsum*2 arr[s1] // 100 x 100 100*2 x
if _, ok := map0[checkSum]; ok {
s2 := map0[checkSum] // j -> y
checkSum = lsum arr[s2]
if _, ok := map0[checkSum]; ok { // 100 * 3 x y
s3 := map0[checkSum] // k -> z
if checkSum arr[s3] lsum == sum {
return true
}
}
}
lsum = arr[s1]
}
return false
}执行结果如下：
图片左神java代码
