题目描述
这是 力扣上的 927. 三等分，难度为 困难。
题目分析
对于本题，是要求我们对 arr 数组（内容是二进制的字符，0 和 1 的序列）进行三等分，对我们的要求是三等分中的数字的二进制的值，三个等分块要相等
思考一：
对于一串二进制序列，咱们需要将其分成三等分，且每一等分的值要相等，那么自然是每一等份的 1 的数量必然是要相等的，咱们对 arr 中每一个数字求和，查看是否可以整除 3 即可，但是 0 的数量不一定相等，因此可以有前导 0
例如
思考二：
那么对于 arr 中的 1 的数字咱们可以进行三等分了，自然也是可以正常找出每一等分的第一个 1 的起始位置，这个就比较好找了
例如，咱们的 arr 中的 1 的个数是 cnt ，那么我们就可以去累加 arr 的每一个数字，让其等于 1 的时候得到 第一个等分块 1 的起始位置为 x，等于cnt3+1\frac{cnt}{3} +13cnt+1的时候得到第二个等分块的其实位置为 y，等于 cnt3∗2+1\frac{cnt}{3}*2 +13cnt∗2+1的时候得到第三个等分块的其实位置为 z
思考三
咱们直接从 x ，y，z 的位置开始向后偏移，直到 z 等于咱们的 arr 数组的长度 n 即可，过程中，咱们每偏移一次，就要去比较 k
最终，k等于 n 的时候，说明咱们第三个等分块已经遍历完毕，这个时候，直接就可以输出结果了，即为 [x-1, y]
咱们这次使用 golang 的方式来进行实现
Golang 的实现方式：
- 先定义咱们的临时函数 myfun ，主要用于找到具体等分的第一个 1 在 arr 中的位置
- 计算 arr 中 1 的个数 cnt，并确认 arr 中是否全都是 0
- 确认 cnt 是否可以正常被 3 整除
- 确认每一等分的对应的位置上的值是都都全部相等
func threeEqualParts(arr []int) []int { // 题目明确需要我们分成 3 等分，此处的 3 等分表示每一份的二进制表示的值相等，并不是元素个数相等 // 题目还表示二进制是可以有前导零的 myfun := func(x int) int{ sum := 0 for i,v := range arr { sum += v if sum == x { return i } } return 0 } // 计算 1 的个数 n := len(arr) cnt := 0 for _,v := range arr { cnt +=v } // 确认 cnt 是否可以整除 3 if cnt %3 !=0 { return []int{-1,-1} } // 如果 cnt 是 0 的情况，例如整个 arr 都是 0 , 那么也是可以正常分成三等分的 if cnt == 0 { return []int{0, n-1} } // 计算每一份的 1 的个数 cnt = cnt / 3 // 找到每一等分第一个 1 开头的位置 x,y,z := myfun(1), myfun(cnt+1), myfun(cnt*2 +1) // 比较三个等分的对应位置上的值是否相等 for ; z<n && arr[x] == arr[y] && arr[y] == arr[z]; x,y,z = x+1, y+1 ,z+1{ } if z == n { return []int{x-1, y} } return []int{-1, -1} }
这种实现方式，时间复杂度是 O(n)，也就是咱们遍历 arr 的长度，空间复杂度是 O(1)
今天就到这里，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
