560.和为K的子数组

链接：560.和为K的子数组
难度：Medium
标签：数组、哈希表、前缀和
简介：给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

题解 1 - javascript

• 编辑时间：2020-05-15
• 执行用时：88ms
• 内存消耗：40.8MB
• 编程语言：javascript
• 解法介绍：由于前 N 项和是前 N-1 项+第 N 项组成，前 N 项和-前 J 项和=K，即前 J 项和=前 N 项和-K。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  const map = new Map().set(0, 1);
  let sum = 0,
    count = 0,
    nowNum;
  for (const num of nums) {
    sum += num;
    nowNum = sum - k;
    if (map.has(nowNum)) count += map.get(nowNum);
    if (map.has(sum)) map.set(sum, map.get(sum) + 1);
    else map.set(sum, 1);
  }
  return count;
};

题解 2 - cpp

• 编辑时间：2021-12-23
• 执行用时：72ms
• 内存消耗：40.7MB
• 编程语言：cpp
• 解法介绍：前缀和。

class Solution {
   public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mmap;
        int sum = 0, ans = 0;
        mmap[0] = 1;
        for (auto& num : nums) {
            sum += num;
            if (mmap[sum - k]) ans += mmap[sum - k];
            mmap[sum]++;
        }
        return ans;
    }
};