算法日常・每日刷题--＜前缀和＞4

560. 和为 K 的子数组 - 力扣LeetCode560. 和为 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 107https://leetcode.cn/problems/subarray-sum-equals-k/因为存在0和负数,用滑动窗口也是不能解决的我们接下来想想前缀和能不能解决问题在于dp数组怎么使用来获得?dp是计算前缀和,那么我们可以用在前面dp数组中,有没有dp[i]-k的值,但是在找那个值的时候选择简单在遍历一遍表和暴力解法没有区别,此时我们可以用哈希表来记录值,这样可以不用遍历.注意点1.当dp[i] k时find dp[i] - k 0如果没有0就统计不到从头开始的子数组2.hash表插入的时机,应该在数据检索一遍后插入,而不是之前就插入.#includeunordered_map class Solution { public: int subarraySum(vectorint nums, int k) { int nnums.size(); vectorint dp(n); dp[0]nums[0]; for(int i1;in;i) { dp[i]dp[i-1]nums[i]; } unordered_mapint,int hash; int count0; //要处理k为o刚好dp[i]k的情况 hash[0]1; for(int i0;in;i) { int finddp[i]-k; if(hash.count(find)0) countcounthash[find]; hash[dp[i]]; } return count; } };