class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> m = new HashMap<>();
        m.put(0, 1);
        return subarraySum(nums, 0, 0, m, k);
    }

    public int subarraySum(int[] nums, int i, int currentSum, Map<Integer, Integer> prefixSumMap, int target) {
        if (i >= nums.length) return 0;
        int res = 0;
        currentSum += nums[i];
        res += prefixSumMap.getOrDefault(currentSum - target, 0);
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);
        res += subarraySum(nums, i + 1, currentSum, prefixSumMap, target);
        // 如果是二叉树，这里会回溯，需要恢复 prefixSumMap
        return res;
    }
}