算法：前缀和，哈希表

抽象一下问题，就是找到所有符合条件的i,j，使得nums[i, j]的和等于k，输出这样的i,j对个数

难点在于想到合适的算法和数据结构来优化暴力枚举算法

关键点在于想到前缀和就是用来处理这种连续区间和的问题的，以及哈希表能够存储频次，利用
$Si - Sj = k$ –> $Sj = Si - k$
这一等式，我们在遍历i的时候，可以用哈希表高效存找符合条件的j

时间复杂度

$O(N)$

代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int ans = 0;
        cnt[0] = 1;
        int n = nums.size();
        int sum = 0;
        for(int i = 0; i < n; i ++){
            sum += nums[i];
            ans += cnt[sum-k];
            cnt[sum] ++;
        }
        return ans;
    }
};