可能性の重複：
Zero sum SubArrayゼロサム最小のサブアレイ
に等しい サブアレイを見つけます。アレイは、正と負の両方の要素を含む、合計0
これはインタビューの質問です。 残念ながら、私はこのquestionへの受け入れられた答えを読むことができませんので、私は再び質問しています：ゼロの合計で最小整数部分配列を見つける方法？
注：これは「ゼロのサブセットの問題」ではありません。明らかなブルートフォース解はO（N^2）（すべてのサブアレイのループ）です。私たちはそれをO（N）で解決できますか？
アレイは、正と負の両方の要素を含む、その和0
はいそれはO（N）で行うことができると等しい サブアレイを見つけます。サブ配列内の要素の合計がゼロに等しい場合、サブ配列の前の最初の要素までの要素の合計が、サブ配列の最後の要素までの要素の合計と同じであることを意味します。
配列を通り、各要素Kに対して、現在の要素までの合計が存在する場合は、合計をKに、インデックスKをハッシュテーブルに入れます。デルタが最小サブアレイ長さよりも小さい場合、最小値を更新します。ハッシュテーブルを（合計、現在のインデックスK）で更新します。
あなたが各要素のハッシュテーブルで検索しているとき、それは本当にO（n）ではありません。 – Detheroc
O（1）同じ合計の最後のインデックスのハッシュテーブル/マップでの検索、合計はマップ内のキーです – BrokenGlass
可能な合計の数が限られている場合のみ。 – Detheroc
このアルゴリズムは、それらすべてを見つけるでしょう、あなたは簡単に最小限の部分配列を見つけるためにそれを変更することができます。
int[] input arrayが与えられた場合、int[] tmpの配列を作成してtmp[i] = tmp[i - 1] + input[i];という配列を作成し、tmpの各要素にその要素までの入力の合計が格納されるようにすることができます。
ここで、tmpをチェックすると、お互いに等しい値があることがわかります。この値がインデックスjとkとであるとすると、合計が0のサブアレイはインデックスj + 1からkになります。注：j + 1 == kの場合、k is 0とそれだけです！ ;）
注：アルゴリズムが実装がBrokenGlassにより示唆されるようにHashMapを使用してなど、さまざまな方法で行うが、上記の注では、特殊なケースに注意してくださいすることができ、仮想tmp[-1] = 0;
を検討すべきです。
例：3 = 0に
int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}
int[] tmp = {4, 10, 13, 4, -1, 0, 3, 3, 5}
もしあなたがそれを欺瞞として見たら質問してください。あなたが答えが不十分であると思うなら、あなたはそれらにコメントしなければなりません、そして/または、この[オリジナルの]質問に恩恵を与えて、注意を喚起してください。 – amit
@amitこの質問でマイケルが述べたように、元の "ゼロ和サブアレイ"の質問は壊れています！受け入れられた答えはもはや利用できないリンクを持っています – Gevorg