16. Subarray Sum Equals K

読了目安 約2分

HashMap / LeetCode 560 (Medium) — 累積和の出現回数を辞書に持ち、和が k の部分配列を数える。

問題

LeetCode 560. Subarray Sum Equals K（Medium / カテゴリ: HashMap）

整数の配列 nums と整数 k が与えられます。 連続する部分配列のうち、和がちょうど k になるものの個数を返します。 要素に負の数を含むので、和の単調性を使う解法は使えません。

考え方

Swift 実装のポイント

• 辞書は [Int: Int] で「累積和 → 出現回数」を持ちます。初期値は [0: 1] です。
• 回数の参照は freq[sum - k, default: 0] で「なければ 0」を短く書けます。
• 「数えてから登録」の順序を守ります。逆にすると k == 0 のとき長さ 0 の区間まで数えてしまいます。

class Solution {
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var count = 0
        var sum = 0
        var freq: [Int: Int] = [0: 1]  // 累積和 → 出現回数
        for num in nums {
            sum += num
            count += freq[sum - k, default: 0]
            freq[sum, default: 0] += 1
        }
        return count
    }
}