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

题目

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例：

  1. 输入:nums = [1,1,1], k = 2
  2. 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

解答 & 代码

思路类似：
★★☆☆未排序数组中累加和为给定值的最长子数组系列问题

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int result = 0;
        int size = nums.size();
        unordered_map<int, int> sumMap;    // 哈希表，存储<从nums[0]加到某个nums[i]的和，这个和的值出现的次数>
        sumMap[0] = 1;                    // 初始化，存入<0,1>
        int sum = 0;                    // 从 nums[0] 到 nums[i] 的加和
        for(int i = 0; i < size; ++i)
        {
            sum += nums[i];
            // 如果当前的和 - k 在哈希表中存在，则说明存在和位 k 的连续子数组
            // 将和位 k 的连续子数组个数加上 sumMap[sum - k]
            if(sumMap.find(sum - k) != sumMap.end())
                result += sumMap[sum - k];

            // 在哈希表中更新当前和出现的次数
            // 如果当前和在哈希表中不存在，则存入次数为1
            if(sumMap.find(sum) == sumMap.end())
                sumMap[sum] = 1;
            else    // 否则次数+1
                ++sumMap[sum];
        }
        return result;
    }
};

执行结果：

执行结果：通过

执行用时：76 ms, 在所有 C++ 提交中击败了 86.13% 的用户
内存消耗：35.1 MB, 在所有 C++ 提交中击败了 90.04% 的用户