相同数量的 0 和 1 算法
Same number of 0s and 1s algorithm
我正在尝试解决以下问题：
Given an binary array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s.
Examples:
Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1}
Output: 1 to 8 (Starting and Ending indexes of output sub array)
我只能想到一个 O(n^2) 的解决方案（即在每个子位置开始一个数组然后检查所有剩余元素是否具有相同数量的 0 和 1 的明显方法）。
有人能想出更好的解决方案吗？
我相信这可以使用权重平衡二叉树结构解决 n O(n)。
关于措辞的一个小小的注释：你说找到 the 最长的子数组，这意味着唯一性，但即使在你的例子中也有不止一个（ 0 到 7 或 1 到8).最好用 "find a subarray of maximal length" 或类似的措辞。但这不是问题。
至于更快的算法，首先通过将 0 的每个实例替换为 -1 来定义一个新数组 swap。这可以在 O(n) 时间内完成。对于您的示例，我们将有
1, -1, 1, 1, 1, -1, -1, -1, 1
现在定义另一个数组 sum，使得 sum[i] 是所有值 swap[0], swap[1], ..., swap[i] 的总和。等价地，
sum[0] = swap[0];
for i > 1, sum[i] = sum[i-1] + swap[i]
这又是 O(n) 时间。所以你的例子变成了
1, 0, 1, 2, 3, 2, 1, 0, 1
现在进行观察。如果 1 的数量等于子数组 (arr[i], ..., arr[j]) 中 0 的数量，那么在第一个新数组中，1 将与相应的 -1 抵消，因此所有值的总和 (swap[i], ..., swap[j]) 将相等到 0。但这等于
swap[0] + swap[1] + ... + swap[j] - (swap[0] + swap[1] + ... + swap[i-1]),
这又等于
sum[j] - sum[i-1].
尽管请注意，如果 i 等于 0，我们必须小心，否则我们将超出数组的范围。这是一个易于实施的检查。
现在我们将问题简化为查找 sum[j] - sum[i-1] 何时等于 0。但这等同于查找值 j 和 i 使得 sum[j] = sum[i-1]。
因为我们知道 sum 中的所有值都位于 -n 和 n 之间（其中 n 是初始数组的大小），您现在可以创建另一个数组对 min max 大小为 2n+1。这里，min 和 max 的索引对应于 sum 的潜在值，其中 min[0] 将包含 i 的最小索引 sum[i] = -n , min[1] 将保存 sum[i] = -n+1 对应的最小索引 i，依此类推。同样，max 将保存最大的索引。这也可以在线性时间内实现。在这一步之后，max[i] 和 min[i] 将对应于 sum[min[i]] = i = sum[max[i]] 的值。
现在你所要做的就是找到 max[k] - min[k] 的最大值，这将为你提供 i = min[k] + 1 和 j = max[k] 的最大子数组的索引，其中包含一个0 和 1 的数量相等。这也是O(n).
我粗略地勾勒了这个，所以当 i = 0 时你必须小心，但这很容易解释。然而，每一步都是 O(n)，所以有更有效的算法。
我正在尝试解决以下问题：
Given an binary array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s.
Examples:
Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1} Output: 1 to 8 (Starting and Ending indexes of output sub array)
我只能想到一个 O(n^2) 的解决方案（即在每个子位置开始一个数组然后检查所有剩余元素是否具有相同数量的 0 和 1 的明显方法）。
有人能想出更好的解决方案吗？
我相信这可以使用权重平衡二叉树结构解决 n O(n)。
关于措辞的一个小小的注释：你说找到 the 最长的子数组，这意味着唯一性，但即使在你的例子中也有不止一个（ 0 到 7 或 1 到8).最好用 "find a subarray of maximal length" 或类似的措辞。但这不是问题。
至于更快的算法，首先通过将 0 的每个实例替换为 -1 来定义一个新数组 swap。这可以在 O(n) 时间内完成。对于您的示例，我们将有
1, -1, 1, 1, 1, -1, -1, -1, 1
现在定义另一个数组 sum，使得 sum[i] 是所有值 swap[0], swap[1], ..., swap[i] 的总和。等价地，
sum[0] = swap[0];
for i > 1, sum[i] = sum[i-1] + swap[i]
这又是 O(n) 时间。所以你的例子变成了
1, 0, 1, 2, 3, 2, 1, 0, 1
现在进行观察。如果 1 的数量等于子数组 (arr[i], ..., arr[j]) 中 0 的数量，那么在第一个新数组中，1 将与相应的 -1 抵消，因此所有值的总和 (swap[i], ..., swap[j]) 将相等到 0。但这等于
swap[0] + swap[1] + ... + swap[j] - (swap[0] + swap[1] + ... + swap[i-1]),
这又等于
sum[j] - sum[i-1].
尽管请注意，如果 i 等于 0，我们必须小心，否则我们将超出数组的范围。这是一个易于实施的检查。
现在我们将问题简化为查找 sum[j] - sum[i-1] 何时等于 0。但这等同于查找值 j 和 i 使得 sum[j] = sum[i-1]。
因为我们知道 sum 中的所有值都位于 -n 和 n 之间（其中 n 是初始数组的大小），您现在可以创建另一个数组对 min max 大小为 2n+1。这里，min 和 max 的索引对应于 sum 的潜在值，其中 min[0] 将包含 i 的最小索引 sum[i] = -n , min[1] 将保存 sum[i] = -n+1 对应的最小索引 i，依此类推。同样，max 将保存最大的索引。这也可以在线性时间内实现。在这一步之后，max[i] 和 min[i] 将对应于 sum[min[i]] = i = sum[max[i]] 的值。
现在你所要做的就是找到 max[k] - min[k] 的最大值，这将为你提供 i = min[k] + 1 和 j = max[k] 的最大子数组的索引，其中包含一个0 和 1 的数量相等。这也是O(n).
我粗略地勾勒了这个，所以当 i = 0 时你必须小心，但这很容易解释。然而，每一步都是 O(n)，所以有更有效的算法。