【力扣hot100】 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二、思路想了一会没啥好思路看了眼标签有前缀和恍然大悟很快就写了一版出来但也是果不其然的卡用例了...问题出在我对前缀和的掌握过于浅薄写的算是暴力前缀和了。问了gpt也才发现sum完全没必要用二重vector挨个存储存储一下每个前缀和的数量即可而此时用unordered_map明显更适宜。那么思路就是mp存储前缀和遍历nums数组用sum-k寻找历史中是否有需要的前缀和有则cnt加上其个数。三、尝试通过的测试用例72 / 93 个MLEclass Solution { public: int subarraySum(vectorint nums, int k) { int cnt0; vectorvectorint sum(nums.size(),vectorint(nums.size(),0)); for(int i0;inums.size();i){ sum[i][i]nums[i]; if(sum[i][i]k){ cnt; } for(int ji1;jnums.size();j){ sum[i][j]sum[i][j-1]nums[j]; if(sum[i][j]k){ cnt; } } } return cnt; } };四、题解class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint,int mp; int cnt0; int sum0; mp[0]1; //如果sum-k0即说明sumk故设为1 for(int i0;inums.size();i){ sumnums[i]; //不需要存储sum一直加就行了 if(mp.count(sum-k)){ //寻找历史有没有需要的前缀和 cntmp[sum-k]; } mp[sum]; } return cnt; } };