零和最小的子阵列

可能重复：
Zero sum SubArray 零和最小的子阵列

一个数组包含正的和负的元素，找到子阵列，其总和等于0

这是一个面试问题。不幸的是，我无法阅读这个question的接受答案，所以我再次问：如何找到零和的最小整数子数组？

请注意，这不是一个“零子集问题”。明显的蛮力解决方案是O（N^2）（遍历所有子阵列）。我们可以用O（N）解决吗？

2012-02-05 Michael

请勿发布问题，如果你看到它作为一个骗局。如果你认为答案不够充分：你应该对他们发表评论和/或在这个[原创]问题上给予奖励以获得更多的关注。 – amit 2012-02-05 19:12:00

@amit在这个问题中，迈克尔所说的原始“零和SubArray”问题被打破了！接受的答案有一个不再可用的链接 – Gevorg 2012-02-05 20:14:27

一个数组包含正的和负的元素，找到子阵列，其总和等于0

是，可以在O（N）来完成。如果子数组内的元素总和等于零，则意味着直到子数组之前的第一个元素的元素总和等于子元素中最后一个元素之前的元素总和。

遍历数组，并且对于每个元素K，将总和K和索引K放入散列表中，如果到当前元素的总和已经存在，则检查该元素和当前元素的索引，如果delta小于最小子数组长度，更新最小值。用（总和，当前索引K）更新散列表。

2012-02-05 19:13:46 BrokenGlass

当你在每个元素的哈希表中搜索时，这并不是真正的O（n）。 – Detheroc 2012-02-05 19:19:17

O（1）使用相同的总和在最后索引的散列表/地图中查找，总和是地图中的关键 – BrokenGlass 2012-02-05 19:24:05

只有当可能的总和数量有限时。 – Detheroc 2012-02-05 19:29:21

这个算法会找到他们所有的，你可以很容易地修改它，找到最小的子阵列。

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

现在，如果您检查tmp，您会注意到可能存在彼此相等的值。假设这个值在索引j和k与j < k，那么总和为0的子阵列将从索引j + 1到k。注意：如果j + 1 == k，那么k is 0就是这样！ ;）

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

实施可以以不同的方式，包括使用一个HashMap通过BrokenGlass的建议，但要小心在上面的注意的特殊情况来实现。

实施例：

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

2012-02-05 20:03:10 Gevorg

回答