当前位置: 首页> 汽车> 时评 > 企业营销策划经营范围_51ppt模板免费下载网站_google关键词排名优化_淘宝seo是什么

企业营销策划经营范围_51ppt模板免费下载网站_google关键词排名优化_淘宝seo是什么

时间:2025/7/11 7:57:46来源:https://blog.csdn.net/qq_45371462/article/details/147618058 浏览次数: 0次
企业营销策划经营范围_51ppt模板免费下载网站_google关键词排名优化_淘宝seo是什么

题面:

在这里插入图片描述

思路:

看到连续非空序列之和,容易想到前缀和计算差分, n u m s nums nums 区间 [ j , i ] [j,i] [j,i] 的和即为: s u m ( i , j ) = p r e [ i ] − p r e [ j − 1 ] sum(i, j) = pre[i] - pre[j-1] sum(i,j)=pre[i]pre[j1]
那么要怎么计算出有多少个区间符合题意 s u m ( i , j ) = = k sum(i,j) == k sum(i,j)==k 呢?

p r e [ i ] pre[i] pre[i] 表示 ∑ j = 0 i n u m s [ j ] \sum_{j=0}^i nums[j] j=0inums[j],即 [ 0 , . . . i ] [0,...i] [0,...i] 区间内所有数的和。

这就转化为,对于每个点 i i i,要求有多少个 j , j ∈ [ 0 , i ] j,j\in[0,i] j,j[0,i] 是满足 s u m ( i , j ) = p r e [ i ] − p r e [ j − 1 ] = k sum(i,j)=pre[i]-pre[j-1]=k sum(i,j)=pre[i]pre[j1]=k,那么就会有多少对区间 [ j , i ] [j,i] [j,i] 对答案有贡献。

对于等式 p r e [ i ] − p r e [ j − 1 ] = k ( i ∈ [ 0 , n ) , j ∈ [ 1 , i ] ) pre[i] - pre[j-1] = k\ (i\in[0,n),j\in[1,i]) pre[i]pre[j1]=k (i[0,n),j[1,i]),可以化为: p r e [ j − 1 ] = p r e [ i ] − k pre[j-1] = pre[i]-k pre[j1]=pre[i]k
这时候我们可以只统计合法的,即只统计前缀和为 p r e [ i ] − k pre[i]-k pre[i]k p r e [ j ] pre[j] pre[j] 有多少个即可。(这时候就转化为力扣 hot 第一题 两数之和了)
写个哈希表 m p mp mp,以前缀和为 k e y key key,出现次数为对应的 v a l val val,记录 p r e [ i ] pre[i] pre[i] 出现的次数。然后从左往右更新 m p mp mp 并统计贡献,那么当前点 i i i 的贡献 m p [ p r e [ i ] − k ] mp[pre[i]−k] mp[pre[i]k] 可在 O ( 1 ) O(1) O(1) 时间内得到。最后的答案即为:以所有下标 i i i 为区间结尾的贡献之和。

注意: 因为已经从左往右遍历更新 m p mp mp 了,所以能保证在当前点 i i i 下统计的 p r e [ j ] pre[j] pre[j] 都是在 i i i 之前的,即 j ∈ [ 0 , i ] j\in[0,i] j[0,i],且每个前缀和 p r e [ i ] pre[i] pre[i] 只和上一个 p r e [ i − 1 ] pre[i-1] pre[i1] 有关,故拿一个临时变量记录 p r e [ i − 1 ] pre[i-1] pre[i1] 即可得到当前 p r e [ i ] pre[i] pre[i]

代码:

int subarraySum(vector<int>& nums, int k) {int cnt = 0, pre = 0;unordered_map<int, int> mp;//考虑pre[i]==k的情况,即pre[j-1]=pre[i]-k=0//所以可将mp[0]初始化为1,当然,也可以直接判断 pre==k?++cnt:next()mp[0] = 1; for(const auto& x : nums) {pre += x;if(mp.find(pre - k) != mp.end())cnt += mp[pre - k];//我们是后推入mp[pre]的,否则如果先 mp[pre]++,则当 k=0 时会出错mp[pre]++;}return cnt;
}
关键字:企业营销策划经营范围_51ppt模板免费下载网站_google关键词排名优化_淘宝seo是什么

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: