560. 和为 K 的子数组

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

解答

class Solution {
public:int subarraySum(vector<int>& nums, int k) {// 前缀和[0, x]：pfs[x] = nums[0] + nums[1] + ... + nums[x];//  ==> nums[x] = pfs[x] - pfs[x-1]// nums的第i到j项和为：// nums[i] + nums[i+1] + ....+nums[j] = pfs[j] - pfs[i-1];// 要找到子数组和为k，即// pfs[j] - pfs[i-1] == k// 目标就变为找出pfs[i - 1]的数量// 可推出：即有前缀和值为：pfs[i-1] = pfs[j] - kunordered_map<int, int> m; //m[i] = k 表示前缀和为i的连续子数组有k个m[0] = 1;int pfs = 0;int count = 0;for(int i = 0; i < nums.size(); ++i){pfs += nums[i]; // [0, i]范围元素的总和if(m.find(pfs - k) != m.end()) //{count += m[pfs - k];}m[pfs] += 1;}return count;}
};