927.三等分

三等分

给定一个由 0 和 1 组成的数组 arr，将数组分成 3 个非空的部分，使得所有这些部分表示相同的二进制值。

如果可以做到，请返回任何 [i, j]，其中 i + 1 < j，这样一来：

• arr[0], arr[1], …, arr[i] 为第一部分
• arr[i + 1], arr[i + 2], …, arr[j - 1] 为第二部分
• arr[j], arr[j + 1], …, arr[arr.length - 1] 为第三部分

如果做不到，就返回 [-1, -1]。

示例 1:

输入：arr = [1,0,1,0,1]
输出：[0,3]

示例 2:

输入：arr = [1,1,0,1,1]
输出：[-1,-1]

提示:

• 3 <= arr.length <= 3 * 10^4
• arr[i] 是 0 或 1

解析

首先统计 1 的数量，如果不能被 3 整除则返回 [-1, -1]。然后找到每个部分的第一个 1 的位置，从后往前确定每个部分的长度，最后比较三个部分是否相同。

var threeEqualParts = function (arr) {
  const ones = arr.reduce((sum, bit) => sum + bit, 0);
  
  if (ones === 0) {
    return [0, arr.length - 1];
  }
  
  if (ones % 3 !== 0) {
    return [-1, -1];
  }

  const onesPerPart = ones / 3;
  let first = -1,
    second = -1,
    third = -1;
  let count = 0;

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 1) {
      count++;
      if (count === 1) first = i;
      else if (count === onesPerPart + 1) second = i;
      else if (count === 2 * onesPerPart + 1) third = i;
    }
  }

  const len = arr.length - third;
  if (first + len > second || second + len > third) {
    return [-1, -1];
  }

  for (let i = 0; i < len; i++) {
    if (arr[first + i] !== arr[second + i] || arr[second + i] !== arr[third + i]) {
      return [-1, -1];
    }
  }

  return [first + len - 1, second + len];
};

时间复杂度 O(n)，空间复杂度 O(1)。