川畅科技联系 网站设计,涟水县住房和城乡建设局网站,百度蜘蛛如何找网站,百度域名地址查询560. 和为 K 的子数组
560. 和为 K 的子数组
题目描述#xff1a;
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的连续子数组的个数 。
子数组是数组中元素的连续非空序列。 解题思路#xff1a; 我们可以很容易想到暴力解法#xf… 560. 和为 K 的子数组
560. 和为 K 的子数组
题目描述
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的连续子数组的个数 。
子数组是数组中元素的连续非空序列。 解题思路 我们可以很容易想到暴力解法但是时间复杂度为N^2我们可以是用前缀和对其优化 我们可以利用前缀和数组sum来记录sum【i】代表到i位置的子数组之和 假设这是0-i的数组后面的我们先不看我们可以将其分成两部分一部分之和为k另外一部分为sum【i】-k本题是求和为k的数组的个数 那问题就可以变为在sum【i】-k中有多少个子数组等于sum【i】-k 这段区间正负都有子区间可能不只有一个噢 我们可以利用hash来完成本题一个参数为前缀和一个参数为次数 都是int类型 我们可以利用一个int变量来代替sum数组因为sum不用每个都记录下来只要记录上一个位置 解题代码
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,inthash;hash[0]1;int ret0;int sum0;for(auto x:nums){sumx;if(hash.count(sum-k))rethash[sum-k];hash[sum];}return ret;}
}; 974. 和可被 K 整除的子数组
974. 和可被 K 整除的子数组
题目描述
给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的连续、非空 子数组 的数目。
子数组 是数组的 连续 部分。 解题思路 解决本题我们先来补充两个知识点 同余定理a-b/pk....0可以转换为a%pb%p具体证明可见同余定理_百度百科 (baidu.com) C中负数a%正数p在C负数求余正数正确应该为正数但是计算结果为负数我们对其修正时期变成a%pp但是为了考虑到正负统一的问题我们再次进行修正让其变为a%pp%p 接下来我们来看一下本题本题如果你做了上一题你会发现基本上是类似的 只不过判断条件不太一样罢了 题目要求的可以被k整除的数组为图中sum-x部分那就变成sum-x%k0也就变成了sum%kx%k也就转为为在【0i-1】这个区间内有多少个前缀和的余数等于sum%k 解题代码
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,inthash;hash[0%k]1;int ret0;int sum0;for(auto x:nums){sumx;int r(sum%kk)%k;if(hash.count(r))rethash[r];hash[r];}return ret;}
};
