零和最小的子陣列

可能重複：
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

回答