做优化需要发多少个网站,南昌电子商务网站建设,婚纱网站策划书模板,网络推广运营公司【LeetCode刷题】Day 16 题目1#xff1a;560.和为k的子数组思路分析#xff1a;思路1#xff1a;前缀和 哈希表 题目1#xff1a;560.和为k的子数组 思路分析#xff1a;
问题1#xff1a;怎样找到数组所有子数组#xff1f;
方式一#xff1a;暴力枚举出来#x… 【LeetCode刷题】Day 16 题目1560.和为k的子数组思路分析思路1前缀和 哈希表 题目1560.和为k的子数组 思路分析
问题1怎样找到数组所有子数组
方式一暴力枚举出来以i开始列出以i开头的所有子数组[i,j]i j size-1再i列出下一个位置开头的所有子数组。
方式二前缀和思想我们用dp[i]来表示[0,i]的数组要找以i结尾的所有子数组只需要 dp[i]-dp[j]0 j i-1 就可以表示所有以i结尾的子数组
下图就这题引入 问题2为什么这样转换
因为在求以i结尾的所有子数组的和时i和k是不变的他们的差值也是固定值所以问题就转换为前缀和为k的数量注意: 0 j i-1
问题3怎样不创建前缀和数组但统计数量
用一个int sum来就可以实现再加上哈希表就能解决这些问题。
思路1前缀和 哈希表
代码实现
class Solution {
public:int subarraySum(vectorint nums, int k) {//前缀和哈希表unordered_mapint,int hash;int sum0 , ret0;//处理当sum[i]本身等于k的情况hash[0] 1;for(auto i : nums){sumi;//判断是否存在值为sum-k的key有就加数量if(hash.count(sum - k)) rethash[sum-k];hash[sum];}return ret;}
};LeetCode链接560.和为k的子数组
