LeetCode/solutions/560. Subarray Sum Equals K.md

# [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)

# 思路

求和为k的连续子数组的个数。因为要求连续子数组，所以我们可以先计算出前缀和`preSum`，然后就可以很方便计算任意区间对应的连续子数组的和`sum[i~j] = preSum[j]-preSum[i]`。要和为k，所以我们可以用一个二重循环遍历前缀和数组`preSum`，但是复杂度为O(n^2)。

更高效的做法是用一个hash表来记录所有前缀和与其出现次数的映射，这样假设当前位置的累加和为`cur_sum`，我们可以通过哈希表快速查找`cur_sum - k`出现的次数。注意hash表初始时要有一个0到1的映射。

时间复杂度O(n)

# C++
``` C++
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int>mp;
        mp[0] = 1;
        
        int cur_sum = 0, res = 0;
        for(int i = 0; i < nums.size(); i++){
            cur_sum += nums[i];
            auto it = mp.find(cur_sum - k);
            if(it != mp.end()) res += it -> second;
            mp[cur_sum]++;
        }
        return res;
    }
};
```