algorithm - 总和为 0 的最大子数组

Question

一个数组同时包含正元素和负元素，找到和为0的最大子数组。

Answer 1

当前接受的答案中的链接需要注册成为成员(member)，但我不了解其内容。

此算法将找到所有子数组的总和为 0，并且可以轻松修改它以找到最小的一个或跟踪开始和结束索引。该算法是O(n)。

给定一个 int[] input数组，你可以创建一个 int[] tmp数组，其中 tmp[i] = tmp[i - 1] + input[i]; tmp 的每个元素将存储直到该元素的输入总和(数组的前缀总和)。

现在，如果您检查 tmp，您会注意到可能存在彼此相等的值。假设此值位于索引 j an k with j < k 处, 然后输入的总和直到 j等于 k 之前的总和这意味着 j 之间的数组部分的总和和 k是0!具体来说，0 和子数组将从索引 j + 1 到 k。

• 注意:如果j + 1 == k , 然后 k is 0就是这样! ;)
• 注意:该算法应考虑虚拟 tmp[-1] = 0 ;
• 注意:一个空数组的总和为 0，而且它是最小的，这种特殊情况也应该在面试中提出。然后面试官会说那不算，那是另外一个问题! ;)

实现可以通过不同的方式完成，包括使用成对的 HashMap，但要注意上面“注意”部分中的特殊情况。

例子:

int[] input = {4,  6,  3, -9, -5, 1, 3, 0, 2}
int[] tmp =   {4, 10, 13,  4, -1, 0, 3, 3, 5}

• tmp 中索引 0 和 3 的值 4 ==> 将 tmp 1 到 3 求和 = 0，长度 (3 - 1) + 1 = 3
• tmp 中索引 5 的值 0 ==> 将 tmp 0 到 5 求和 = 0，长度 (5 - 0) + 1 = 6
• tmp 中索引 6 和 7 的值 3 ==> 将 tmp 7 与 7 相加 = 0，长度 (7 - 7) + 1 = 1

****更新****

假设在我们的 tmp 数组中，我们最终得到具有相同值的多个元素，那么您必须考虑其中的每个相同对!示例(请记住索引“-1”处的虚拟“0”):

int[] array = {0, 1, -1, 0}
int[] tmp = {0, 1, 0, 0}

通过应用上述相同的算法，0-sum 子数组由以下索引(包括在内)分隔:

[0] [0-2] [0-3] [1-2] [1-3] [3]

尽管具有相同值的多个条目的存在可能会根据实现影响算法的复杂性，但我相信通过在 tmp 上使用倒排索引(将值映射到它出现的索引)我们可以保持运行时间为 O(n)。