HashMapに合計と頻度を格納する直観

Question

整数の配列と別の数kが与えられており、合計がkに等しい連続するサブアレイの合計数を見つける必要があります。私はLeetCode上で、次の興味深いコードスニペットを見つけました：

public class Solution { 
    public int subarraySum(int[] nums, int k) { 
     int count = 0, sum = 0; 
     HashMap < Integer, Integer > map = new HashMap < >(); 
     map.put(0, 1); 
     for (int i = 0; i < nums.length; i++) { 
      sum += nums[i]; 
      if (map.containsKey(sum - k)) 
       count += map.get(sum - k); 
      map.put(sum, map.getOrDefault(sum, 0) + 1); 
     } 
     return count; 
    } 
} 

私は効率的なソリューションが好きで、私はそれを理解しようとしています。しかし、私は2つの質問があります。

1. をHashMapの中の現在sumとそのfrequencyを格納背後にある直感は何ですか？
2. 検出されたサブアレイが連続していることを保証するものは何ですか？

サンプル入力：[1,1,1]およびk = 2;
出力：2

Answer 1

ニースアルゴリズム。 sum(1, i) = sum(1, j) + sum(j + 1, i)（私はそれが通常の数学表記で、ここでのJavaを使用していない） それはどのiとjのために真である：

は単純な事実から始めることができます。

すべてsum(j+1, i)はkと同じです。あなたのプログラムsum(1, i)で

sum(1, i) = sum(1, j) + kまたはsum(1, i) -k = sum(1, j)を見つけることと同じである

はsum変数です。だから、jにはsum -k = sum(1, j)が真であることを確認する必要があります。うまくいけば、私たちはsum(1, j)を鍵としてmapに持っています。

私たちはmap.containsKey(sum - k)をチェックし、それが当てはまる場合は、必要な合計を与えるようなjがあります。

どのように多くの異なる方法でその合計を得るかを数えるには値が必要です。

PS：BTWすべての値が負でない場合、より良いアルゴリズムがあります。余分なメモリを必要としません。

PPSは：また、私は8

for (int num : nums) { 
     sum += num; 
     count += map.getOrDefault(sum - k, 0); 
     map.compute(sum, (key, value) -> (value == null) ? 1 : value + 1); 
    } 

Answer 2

我々はnums[]配列をスキャンすると、mapは、我々は特定のsum（sum手段を見てきました何回含まれていますJavaの場合、あなたにはあなたのコードにいくつかの改善をしました数字を最初から現在まで合計する）。

さて、任意の時点で、ifで、私たちが見た場合、mapはsum-k X回が含まれており、現在の合計は、我々は合計kとX異なるサブアレイを見つけたことを、我々は知っている、sumであること。 sumには最初から現在までの合計が含まれており、mapは開始点から始点までの合計でインデックス付けされているためです。 mapに1より大きい値が含まれている場合は、一定の合計が複数回発生することを意味します（num[]にゼロまたは負の数がある場合に発生する可能性があります）。見つかった部分配列は、この「特定の」点から現在の位置までであるため、連続していなければなりません。

Answer 3

3キーの事：

• 最初のキーは、キーsum - kがすでにマップにそれが

周波数だと、それぞれの和をマッピングするために入れ

である場合にのみ、0

増加countです

私は3つの場合に分けます：

1番目：0より大きい数字。

各キーの周波数は1になります。
どのようにカウントが増加しましたか？キーが既に地図にあった場合にのみ増加します。 キーはすべて前の合計です。したがって、条件if (map.containsKey(sum - k))の現在の鍵はsum - kです。 sum - kがキーの場合は、前回の合計（sum - k）と現在の合計が合計がk（原因はk + (sum - k) = sum - 現在の値）の要素であることを意味します。だから我々はcountを増やすことができる - 我々はサブアレイを見つけた。

第2位：数値は0以上です。
これで、間にゼロを置くことができました。多くの違いはありませんが、countを増やして次のステップではnumsの配列に0を設定するとどうなりますか想像することができます。
この場合、私たちはcountを再び正常に増加させます。

ゼロを含めると、頻度が変更されます。この例を想像してみましょう： subarraySum({0, 0, 0, 7, 0}, 7);結果は8です。 最初のキーは0であることを覚えておいてください。私たちが反復するとき、私たちは7になります。(0: 4)のマップがあります。今度はsum = 7と7 - 7 = 0なので、3つあるので、この回数はこの頻度で増加しました。今、私たちは、配列から最後の要素を選んでいる - このキーの0の値は、まだsum - k 4であるので、再び私たちのcountは4

第三増加し、まだ同じです：整数。
私はあなたがポイントを得ると思う;）この時間は負の数もいくつかの頻度を増加させる可能性があります。 マップにsum - keyというキーがある場合は、前回の合計（sum - k）と整数の合計がk（原因はk + (sum - k) = sum - 現在の値）であることを意味します。もしそうなら、度数を増やしてみましょう。