560. Subarray Sum Equals K

O(n) 在遍历每个数的过程中用hashmap把已经算过的前缀和存起来，之后只需要查看目标前缀和的个数即可
初始化要加入{0,1}这对映射，这是为啥呢，因为我们的解题思路是遍历数组中的数字，用sum来记录到当前位置的累加和，我们建立哈希表的目的是为了让我们可以快速的查找sum-k是否存在，即是否有连续子数组的和为sum-k，如果存在的话，那么和为k的子数组一定也存在，这样当sum刚好为k的时候，那么数组从起始到当前位置的这段子数组的和就是k，满足题意，如果哈希表中事先没有m[0]项的话，这个符合题意的结果就无法累加到结果res中，这就是初始化的用途

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> m{{0, 1}};
        int s = 0, res = 0;
        for (int x : nums) {
            s += x;
            res += m[s - k];
            ++m[s];
        }
        return res;
    }
};

O(n²)

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