arrays - 查找具有相同数量的 0's and 1' 的最大子数组

Question

所以，我有一个只包含 0 和 1 的数组。我必须找出包含相同数量的 0 和 1 的最大子数组。一种可能是一种天真的方法，其复杂度为 O(n^2)，其中我获取外循环中的每个元素并计算内循环中可能的子数组，并不断更新最大大小(如果找到)。我可以使用其他更好的方法(比如 O(n))吗？谢谢!

Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)

Answer 1

这是一个 O(n) 时间、O(n) 空间算法。我不确定它是否是最优的，但它胜过二次方时间。

基本思路如下。假设你从数组的左边扫描到右边记录，在每一步中，1 的数量和 0 的数量之间的差异。如果您在每一步都写出这些值，您将得到如下结果:

  1,   0,   1,    0,    0,   0,   0
0,   1,   0,   1,    0,    -1,  -2,  -3

如果您有一个包含相同数量的 0 和 1 的子数组，则子数组开头的 0 和 1 的净差将等于子数组之后的净数。因此，这个问题可以重新定义为试图在辅助数组中找到两个相等且距离尽可能远的相等值。

好消息是数组中的每个条目都在 -n 和 +n 之间，因此您可以制作一个 2n+1 元素表并将每个数字第一次出现和最后一次出现的索引存储在其中。从那里，很容易找到最长的范围。总的来说，这需要 O(n) 的空间，并且可以在 O(n) 的时间内填充和搜索所有内容。

希望这对您有所帮助!