PrefixSum_Leetcode_560. Subarray Sum Equals K [swift]

https://leetcode.com/problems/subarray-sum-equals-k/description/

 

누적합 문제의 이론은 대략 이해를 했다. 라고 생각했는데,,

문제를 계속 풀면서 이해를 더하고 체화시키는게 목표

재귀탐색코드

class Solution {
    
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var sol = 0
        var map = [Int: Int]()
        map[0] = 1    

        func recursive(curIdx: Int, pastSum: Int) {
            guard curIdx < nums.count else { return }
            let curSum = pastSum + nums[curIdx]
            sol += map[curSum - k, default: 0]
            map[curSum, default: 0] += 1

            recursive(curIdx: curIdx + 1, pastSum: curSum)
            map[curSum]! -= 1
        }

        recursive(curIdx: 0, pastSum: 0)
        return sol
    }

}

모범코드

class Solution {
    
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var sol = 0
        var map = [Int: Int]()
        map[0] = 1    

        var sum = 0

        for i in 0..<nums.count {
            sum += nums[i]
            sol += map[sum - k ,default: 0]
            map[sum, default: 0] += 1
        }   
        
        return sol
    }

}