网站的详情页面,企业网站的基本特点是什么,佛山营销网站开发,品划网络做营销型网站560. 和为 K 的子数组 - 力扣#xff08;LeetCode#xff09; 因为是判断子数组的和 要返回 k 的次数#xff0c;所以
解法#xff1a;前缀和 哈希表
提出一个概念#xff1a;以下标i为结尾的所有子数组 那要找出所有和 k的子数组 就相当于#xff1a;找出所有值为…560. 和为 K 的子数组 - 力扣LeetCode 因为是判断子数组的和 要返回 k 的次数所以
解法前缀和 哈希表
提出一个概念以下标i为结尾的所有子数组 那要找出所有和 k的子数组 就相当于找出所有值为dp[i] - k的子数组。 dp[i] - k就是一段区间的前置和了只要把所有以下标i为结尾的所有子数组的前缀和丢到哈希表中最后返回 dp[i] - k (前提要存在)出现的次数即可。
细节
1.前缀和什么时候丢入哈希表 因为放进去的是前缀和放[0,i]的话到了[0,i1]就会重复所以到i下标时先放入[0,i-1]的前缀和再加入自己。(dp[i])
2.不用真的创建一个前缀和数组
dp[i] sum nums[i] 所以只需要一个sum代表前一次的前缀和每次算完前缀和把sum更新就行了。
3.如果到自己的前缀和是k呢(dp[i] k) 那范围就是[0,-1]显然不行所以默认让hash[0] 1
class Solution
{
public:int subarraySum(vectorint nums, int k) {unordered_mapint,int hash;hash[0] 1;int sum 0,count 0;for(auto e : nums){sum e;if(hash.count(sum-k))count hash[sum - k];//存完[0,i-1]后再存自己hash[sum];}return count;}
};
