总和等于0的最大子数组 [英] maximum subarray whose sum equals 0

问题描述

一个包含正负元素的数组，找到总和等于0的最大子数组。

An array contains both positive and negative elements, find the maximum subarray whose sum equals 0.

推荐答案

当前接受的答案中的链接要求注册成员身份，而我不接受其内容。

此算法将找到所有总和为0的子数组，并且可以轻松修改以找到最小的索引或跟踪起始索引和结束索引。此算法为 O（n）。

This algorithm will find all subarrays with sum 0 and it can be easily modified to find the minimal one or to keep track of the start and end indexes. This algorithm is O(n).

给出一个 int []输入数组，您可以创建一个 int [] tmp 数组，其中 tmp [i] = tmp [i-1] + input [i]; tmp的每个元素将存储该元素的输入总和（数组的前缀总和）。

Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element(prefix sum of array).

现在，如果选中tmp，您将请注意，可能存在彼此相等的值。假设此值位于索引 j a k且j< k ，则直到 j 的输入总和等于直到 k 的总和这意味着 j 和 k 之间的数组部分的总和为0！具体来说，总和为0的子数组将从索引j + 1到k。

Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.

• 注意：如果 j + 1 = = k ，则 k为0 就是这样！ ;）


• 注意：算法应考虑虚拟 tmp [-1] = 0 ;


• 注意：一个空数组的总和为0，这是最小的，这种特殊情况也应在采访中提出。然后，面试官会说这不算什么，但这是另一个问题！ ;）

• NOTE: if j + 1 == k, then k is 0 and that's it! ;)
• NOTE: The algorithm should consider a virtual tmp[-1] = 0;
• NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)

该实现可以通过不同的方式完成，包括使用带有对的HashMap，但要注意NOTE部分中的特殊情况

The implementation can be done in different ways including using a HashMap with pairs but be careful with the special case in the NOTE section above.

示例：

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



****更新****

****UPDATE****

假设在我们的tmp数组中我们最终如果多个元素具有相同的值，则必须考虑其中的每个相同对！示例（请记住索引'-1'处的虚拟'0'）：

Assuming that in our tmp array we end up with multiple element with the same value then you have to consider every identical pair in it! Example (keep in mind the virtual '0' at index '-1'):

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

通过应用上述相同的算法，零和子数组由以下索引（包括）定界：

By applying the same algorithm described above the 0-sum subarrays are delimited by the following indexes (included):

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

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

Although the presence of multiple entries with the same value might impact the complexity of the algorithm depending on the implementation, I believe that by using an inverted index on tmp (mapping a value to the indexes where it appears) we can keep the running time at O(n).

这篇关于总和等于0的最大子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！