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