LeetCode 927：三等分二进制数组（C 语言版）

题目描述

给定一个仅由 0 和 1 组成的整数数组 arr，要求将其分割成三个非空部分，使得这三个部分所代表的二进制数值完全相等。

如果可能，返回任意满足条件的 [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,0] 代表十进制的 6，而不是 3。前导零是允许的，因此 [0,1,1] 和 [1,1] 代表相同的值。

如果无法实现，返回 [-1, -1]。

示例：

• 输入：arr = [1,0,1,0,1]，输出：[0,3]
• 输入：arr = [1,1,0,1,1]，输出：[-1,-1]
• 输入：arr = [1,1,0,0,1]，输出：[0,2]

约束条件：

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

---

解题思路

这道题的核心在于理解'二进制数值相等'的含义。由于允许前导零，关键在于有效数字部分（即从第一个 1 开始到末尾）必须一致，同时各部分之间的间隔要能容纳第三部分所需的尾部零。

1. 统计 1 的总数：首先遍历数组，计算 1 的总个数。如果 1 的总数不能被 3 整除，那么显然无法将数组分成三个数值相等的部分，直接返回 [-1, -1]。
2. 处理全零情况：如果数组中没有 1（即总数为 0），那么任何分割方式都能满足条件（因为 0 等于 0）。此时可以简单返回 [0, arrSize - 1]。
3. 确定基准长度：设每个部分应包含的 1 的数量为 k = totalOnes / 3。找到每一部分的第一个 1 的位置，分别记为 s1, s2, s3。由于三部分的数值必须相等，它们从第一个 1 开始直到数组末尾的模式必须完全一致。这意味着第三部分从 s3 到末尾的长度 len，就是我们需要匹配的有效模式长度。
4. 验证模式一致性：比较 arr[s1...s1+len-1]、arr[s2...s2+len-1] 和 arr[s3...s3+len-1]。如果有任何位不匹配，说明无法分割，返回失败。
5. 检查间隔：即使模式匹配，还需要确保第一部分和第二部分之间有足够的空间来容纳第三部分末尾的零。具体来说，第一部分的结束位置 i 和第二部分的开始位置 j 需要满足一定的间距关系，保证 i 之后到 s2 之前，以及 j 之后到 s3 之前的区域能够容纳必要的尾部零。

---

代码实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int*  {
    *returnSize = ;
    * ans = (*)( * ());
    ans[] = ;
    ans[] = ;

    
     totalOnes = ;
     ( i = ; i < arrSize; ++i) {
        totalOnes += arr[i];
    }

    
     (totalOnes == ) {
        ans[] = ;
        ans[] = arrSize - ;
         ans;
    }

    
     (totalOnes %  != ) {
         ans;
    }

     k = totalOnes / ;

    
     s1 = , s2 = , s3 = ;
     cnt = ;
     ( i = ; i < arrSize; ++i) {
         (arr[i] == ) {
            ++cnt;
             (cnt == ) s1 = i;
              (cnt == k + ) s2 = i;
              (cnt ==  * k + ) s3 = i;
        }
    }

    
     len = arrSize - s3;

    
     ( t = ; t < len; ++t) {
         (arr[s1 + t] != arr[s2 + t] || arr[s1 + t] != arr[s3 + t]) {
             ans; 
        }
    }

    
    
     iIdx = s1 + len - ;
    
     jIdx = s2 + len;

    
    
     (iIdx < s2 && jIdx <= arrSize - ) {
        ans[] = iIdx;
        ans[] = jIdx;
    }

     ans;
}