题目链接：点击跳转
题目意思
题目需要你帮他把这个arr序列分成连续的三段序列，序列是由0、1组成，每段的0、1序列组成的二进制数都要相等。你只需要找到第一段序列与第二段序列的分割点 i, 第二段序列与第三段序列的分割点j。
思路
方法一、双指针
这题目要求我们分成三等分的且二进制数相等序列。
- 1的个数一定得是能被 3 整除的，否则肯定无法三等分。cnt = 1的个数 / 3
- 我们先用双指针i、j取前后两部分刚好cnt个1的序列。
。从0开始的startI表示去前置零后的第一段序列的二进制数开头，与我们的第三段序列的二进制数开头进行对比，如果出现不相等则不能三等分，否则 startI就是第一段与第二段序列的分割点i。
。我们确定了i是第一段与第二段序列的分割点后，第二段序列的开头则是从i + 1开始的，需要先得到去掉第二段序列的前置零的二进制数开头 idy，与第一段序列去对比，如果出现不相等则不能三等分，否则 idy就是第二段与第三段序列的分割点j。
代码示例：
func threeEqualParts(arr []int) []int { cnt := 0 //统计1的个数 for _, v := range arr { if v == 1{ cnt++ } } if cnt % 3 != 0{ return []int{-1, -1} }else if cnt == 0{ //如果没有0怎么分配都行，但是只能输出{0, n - 1}才对 return []int{0, len(arr) - 1} } n := cnt / 3 i := 0 for x := 0; x < n; i++{ x += arr[i] } j := len(arr) - 1 for x := 0; x < n; j--{ x += arr[j] } startI := 0 for arr[startI] == 0{ startI++ } idx := startI startJ := j + 1 //确定前后两部分的去前置零的序列长度，并判断是否相等，找到I的位置 for ; startJ < len(arr); startI, startJ = startI + 1, startJ + 1 { if arr[startI] != arr[startJ] { return []int{-1, -1} } } //确定了I的位置 i = startI - 1 //去掉{I, ?}序列的前导零 idy := i + 1 for arr[idy] == 0 { idy++ } //确定J的位置 for ; idx <= i; idx, idy = idx + 1, idy + 1 { if arr[idx] != arr[idy] { return []int{-1, -1} } } j = idy return []int{i, j} }
复杂度分析
- 时间复杂度：O(N + i + j)，其中N表示arr序列的长度，遍历一遍数组需要O(N)的时间。i 表示 第一段序列的结尾，找到i需要O(i)的时间。j 表示 第二段序列的结尾，找到j需要O(j)的时间。
- 空间复杂度：O(1)，不需要额外申请空间。
