力扣第560题 和为k的子数组

前言

记录一下刷题历程 力扣第560题 和为k的子数组

和为k的子数组

原题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2

分析

我们可以计算前缀和如下图所示。

当我们知道前缀和后，我们想要知道和为k的子序列 我们值需要对前缀和数组进行相减，前缀和数组中有6 我们发现前缀和数组中6-0=6，而这个6-0指的就是连续子序列0 1 2 3。我们再看下一个21，我们发现21-15=6，而这个21-15指的就是子序列6。这样我们就可以通过前缀和来求解

代码如下：

class Solution {
public:
    // 定义函数 subarraySum，接受一个整数数组 nums 和一个目标值 k
    int subarraySum(vector<int>& nums, int k) {
        // 创建一个哈希表 map，用于记录前缀和出现的次数
        unordered_map<int,int> map;
        
        // sum 用于记录当前的前缀和，res 用于记录和为 k 的子数组的数量
        int sum = 0, res = 0;
        
        // 初始化哈希表，表示前缀和为 0 的情况出现了 1 次
        // 这是为了处理子数组本身就等于 k 的情况
        map[0]++;

        // 遍历数组中的每个元素
        for (auto n : nums) {
            // 更新前缀和，sum 记录到当前位置的数组元素的累加和
            sum += n;

            // 判断当前前缀和减去 k 的值是否在哈希表中
            // 如果存在，说明找到了一个子数组，其和为 k
            if (map.count(sum - k)) {
                // 如果找到了这样的前缀和，累加它的出现次数到结果中
                // 这意味着存在 map[sum - k] 个子数组的和等于 k
                res += map[sum - k];
            }

            // 更新哈希表，记录当前前缀和 sum 的出现次数
            // 如果 sum 已经存在，次数加 1；否则新增该前缀和，次数为 1
            map[sum]++;
        }

        // 返回最终找到的子数组个数
        return res;
    }
};

总结

1.前缀和：

我们用一个变量 sum 来记录当前元素之前所有元素的累加和，也就是前缀和。前缀和可以帮助我们快速计算某一段子数组的和。

2.哈希表的作用：

我们使用一个哈希表 map 来存储前缀和出现的次数。这样，当我们计算到某个位置时，可以通过查找 sum - k 是否存在于哈希表中，来确定之前是否有一段子数组的和等于 k。

3.子数组和等于 k 的判断：

对于每个元素，计算当前前缀和 sum。我们想找到某一段子数组的和等于 k，可以用当前前缀和减去目标值 k，如果 sum - k 出现在哈希表中，意味着从某个起始位置到当前的位置的子数组和为 k。因此，将其出现的次数累加到结果中。

4.特殊处理：

在一开始，我们往哈希表中加入了 map[0] = 1，这是为了处理前缀和刚好等于 k 的子数组（即从数组开始的子数组）的情况。