PROBLEM 06
合計が目標になる連続区間
合計が target になる連続部分配列の個数を数えます。
日ごとの増減値が配列で与えられます。
連続する1日以上の区間のうち、合計が target と等しくなる区間はいくつあるでしょうか。
subarraySum(nums, target) は区間の個数を返してください。
同じ位置を含む区間同士が重なっていても、それぞれ数えます。
例
入力: nums = [1, 2, 1, 2], target = 3
出力: 3
理由: [1,2]、[2,1]、[1,2] の3区間入力: nums = [0, 0, 0], target = 0
出力: 6制約
1 <= nums.length <= 100,000- 各要素と
targetは安全な整数 - 配列には負数と0を含む
STEPWISE HINTS
ヒント
01考え方の方向
各位置までの累積和を考えます。2つの累積和の差が target なら、その間の区間が答えです。
02使うデータ構造
現在の累積和を prefix とすると、過去に prefix - target が何回あったかが、今の位置で終わる区間数です。
03擬似コード
freq = Map([[0,1]]) から始める。prefix を更新し、freq.get(prefix-target) を答えに足してから、freq[prefix] を増やす。
AFTER ACCEPTED
解説
AC 後に解説が開きます
まずは自分の言葉で方針を説明し、コードに落としてみましょう。