wordpress建站ftp,潍坊最近最新消息,企信网查询,怎么做asp网站1. 题目解析
题目链接#xff1a;560. 和为 K 的子数组 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了。
核心在于计算题目所给数组是否存在连续子数组和为指定值#xff0c;存在返回连续子数组个数即可#xff0c;不存在返回0即…1. 题目解析
题目链接560. 和为 K 的子数组 这个问题的理解其实相当简单只需看一下示例基本就能明白其含义了。
核心在于计算题目所给数组是否存在连续子数组和为指定值存在返回连续子数组个数即可不存在返回0即可。
2.算法原理
要计算以数组中的位置i为结尾的和为k的子数组数量我们首先需要理解前缀和的概念。sum[i]代表从数组起始位置到位置i包括i之间所有元素的和。为了找到这样的子数组我们需要确定有多少起始位置x1, x2, x3, ...使得从x到i的区间内所有元素的和恰好为k。
这意味着如果我们考虑从位置0到x不包括x1的区间其和应该是sum[i] - k。因此问题转化为在[0, i - 1]的区间内查找有多少个前缀和等于sum[i] - k。
为了高效地解决此问题我们不需要真的初始化一个前缀和数组因为只关心在位置i之前哪些前缀和的值等于sum[i] - k。因此我们可以使用一个哈希表来跟踪在遍历数组时每种前缀和出现的次数。这样在遍历到位置i时我们只需查看哈希表中键为sum[i] - k的值这个值就代表了以位置i为结尾的和为k的子数组的数量。
总的来说我们的策略是
遍历数组同时计算当前位置的前缀和。使用哈希表来存储之前计算过的前缀和及其出现的次数。在每个位置i查找哈希表中键为sum[i] - k的值该值即为以i为结尾的和为k的子数组数量。 3.代码编写
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int hash;hash[0] 1;int ret 0, sum 0;for(auto x : nums){sum x;if(hash.count(sum - k)) ret hash[sum - k];hash[sum];}return ret;}
};
The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
