给定一个正数数组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编写。代码如下:
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
}
执行结果如下: