题目
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2
示例 2：
输入：nums = [1,2,3], k = 3 输出：2
解题
方法一：前缀和（超时）
class Solution { public: int subarraySum(vector<int>& nums, int k) { int n=nums.size(); vector<int> preSums(n+1); for(int i=0;i<nums.size();i++){ preSums[i+1]=preSums[i]+nums[i]; } int count=0; for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ if(preSums[i]-preSums[j]==k){ count++; } } } return count; } };
方法二：前缀和+哈希表
红色部分就是我们要求的和为k的子数组
如果当前遍历到的前缀和是presum，那么只要知道presum-k的个数就行了，对最后结果加上presum-k的个数
通过map去维护一个前缀和 的个数
class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int,int> map; map[0]=1;//前缀和为0的个数为1 int preSum=0; int count=0; for(int num:nums){ preSum+=num; if(map.count(preSum-k)){//加上前缀和为preSum-k的个数 count+=map[preSum-k]; } map[preSum]++; } return count; } };
