查找数目相等的0和1的最大子数组

因此，我有一个仅包含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)

这是O（n）时间，O（n）空间算法。我不确定这是否是最佳选择，但它超过了二次时间。

基本思想如下。假设您在每一步中从数组的左侧扫描到右侧的记录，分别是1s和0s之间的差。如果在每个步骤中写出这些值，都会得到如下所示的信息：

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）时间内进行填充和搜索。

希望这可以帮助！