【Leetcode每日一题】前缀和 - 和为 K 的子数组（难度⭐）（29）

1. 题目解析

题目链接：560. 和为 K 的子数组

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

核心在于计算题目所给数组是否存在连续子数组和为指定值，存在返回连续子数组个数即可，不存在返回0即可。

2.算法原理

要计算以数组中的位置i为结尾的和为k的子数组数量，我们首先需要理解前缀和的概念。sum[i]代表从数组起始位置到位置i（包括i）之间所有元素的和。为了找到这样的子数组，我们需要确定有多少起始位置x1, x2, x3, ...，使得从x到i的区间内所有元素的和恰好为k。

这意味着，如果我们考虑从位置0到x（不包括x+1）的区间，其和应该是sum[i] - k。因此，问题转化为在[0, i - 1]的区间内，查找有多少个前缀和等于sum[i] - k。

为了高效地解决此问题，我们不需要真的初始化一个前缀和数组，因为只关心在位置i之前，哪些前缀和的值等于sum[i] - k。因此，我们可以使用一个哈希表来跟踪在遍历数组时，每种前缀和出现的次数。这样，在遍历到位置i时，我们只需查看哈希表中键为sum[i] - k的值，这个值就代表了以位置i为结尾的和为k的子数组的数量。

总的来说，我们的策略是：

遍历数组，同时计算当前位置的前缀和。
使用哈希表来存储之前计算过的前缀和及其出现的次数。
在每个位置i，查找哈希表中键为sum[i] - k的值，该值即为以i为结尾的和为k的子数组数量。

3.代码编写

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1;
        int ret = 0, sum = 0;
        for(auto x : nums)
        {
            sum += x;
            if(hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};