零和子数组 [英] Zero sum SubArray

问题描述

这是数组包含正反两方面的内容，查找其子阵 之和等于0。

An array contains both positive and negative elements, find the 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 [我 - 1] +输入[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.

现在，如果你检查tmp目录，你会发现，有可能是彼此相等的值。比方说，这个值是在指数 j表示使用J＆LT的K表;氏/ code>，然后输入到总和Ĵ等于总和，直到 K 这意味着数组中的一部分Ĵ和 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 ==氏/ code>，然后 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成对，但要小心在上面的注意部分的特殊情况来实现。

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}

• 值4 tmp目录索引0和3 ==>之和TMP 1至3 = 0，长度（3 - 1）+ 1 = 4
• 值0 tmp目录索引5 ==>之和TMP 0-5 = 0，长度（5 - 0）+ 1 = 6
• 值3 tmp目录索引6和7 ==>之和TMP 7到7 = 0，长度（7 - 7）+ 1 = 1

更新

假设在我们的TMP数组中，我们结束了多个元素具有相同的值，那么你必须要考虑每一个相同的对的吧！示例（请记住虚拟'0'指数'-1'）

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}

通过应用上面的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]

虽然多个条目具有相同值的presence可能会影响取决于实现的算法的复杂性，相信通过使用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).

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