// MARK: - 560. Subarray Sum Equals K
// Используем словарь, где ключ - префиксная сумма, а значение кол-во раз сколько получилась префиксаня сумма


func subarraySum(_ nums: [Int], _ k: Int) -> Int {

    // Базовый случай префиксной суммы, когда пустой префиксный подмассив и сам подмассив суммой k
    var prefixSumDict: [Int:Int] = [0:1]

    var sum = 0
    var result = 0

    for num in nums {
        sum += num

        // если мы можем удалить из sum префикс dif и получить k, то это то что нужно и по словарю смотрим сколько раз это можем сделать
        // k = sum - dif

        var dif = sum - k

        // Проверяем есть ли этот префикс в словаре (как бы проаеряем можем ли мы удалить из массива dif и получить k)
        if prefixSumDict[dif] != nil {
            result += prefixSumDict[dif]!
        }

        prefixSumDict[sum, default: 0] += 1
    }
    return result
}
subarraySum([1,2,3], 3)