subarray-sum-equals-k(Leetcode.560)



Subarray Sum Equals K Leetcode



トピックリンク Leetcoee.560
問題は、配列から、kに等しいサブ配列の合計がいくつあるかを調べることです。
誰もが暴力的な解決策を考えることができ、O(N ^ 2)の複雑さはTLEです。長い間考えていたのですが、まだわかりません。私は他の人の解決策を見に行きました。この問題の解決策は実際には非常に簡単です。インターネット上の非常に多くのバージョンにも統合コアがあります。しかし、このコアはあまりよく理解されていません。たとえば、コードを長時間見るとよくわかりません。最後に、例を使用してプログラムを手動で実行し、理由を理解しました。だからここに記録してください。
例として、タイトルのデフォルトのテストケースを取り上げます。

nums = [1,1,1] k = 2 // variable initialization int cum = 0 // cumulated sum map rec // prefix sum recorder int cnt = 0 rec[0]++

プログラムの実行中に、0からiまでの配列要素の合計が計算され、cum変数に配置されます。各cumに対応する値は、マップ変数recにカウントされます。これにより、配列を複数回トラバースする必要がなくなります。ソリューションの重要なステップ。 Cntは、返される必要のある結果を記録します。
プログラムのコアループコードは次のとおりです。



for(int i = 0 i

実行中の変数の変化は次のとおりです。

nums 1 1 1 sum 1 2 2 rec (1,1) (2,1) (3,1) cnt 0 0 1

forループのより厄介な文はcnt += rec[cum-k]であり、以下で詳細に説明します。
sum [i、j]を、配列内の添え字i + 1からjのサブ配列の要素の合計とし、pre_sum(i)を配列内の添え字0からiとします。サブ配列の要素の合計の値、次にsum [i、j] = pre_sum(j)-pre_sum(i)。次に、条件を満たすサブ配列のsat [i、j] = k、つまりk = pre_sum(j)-pre_sum(i)をコードに変換します。



pre_sum(j) - k= pre_sum(i)

コードrec [cum-k]は、明らかにステートメントに渡されたpre_sum(i)の数を記録します。rec[cum]++ cntカウントの目的を達成するために、pre_sum(i)の発生数を記録します。
これがこの問題の解決策です。すべてのコードは次のとおりです(letetcodeの説明を参照)

class Solution { public: int subarraySum(vector& nums, int k) { int cum = 0 map rec // prefix sum recorder int cnt = 0 rec[0]++ for(int i = 0 i