在百度上做个网站需要多少钱,去掉wordpress顶部,网站后台收入怎么做会计分录,国内出名网站建设设计公司题目#xff1a;
给定一个整数数组 nums 和一个整数 k #xff0c;返回其中元素之和可被 k 整除的#xff08;连续、非空#xff09; 子数组 的数目。
子数组 是数组的 连续 部分。 示例 1#xff1a;
输入#xff1a;nums [4,5,0,-2,-3,1], k 5
输出#xff1a;7
…题目
给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的连续、非空 子数组 的数目。
子数组 是数组的 连续 部分。 示例 1
输入nums [4,5,0,-2,-3,1], k 5
输出7
解释
有 7 个子数组满足其元素之和可被 k 5 整除
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]示例 2:
输入: nums [5], k 9
输出: 0提示:
1 nums.length 3 * 104-104 nums[i] 1042 k 104
算法原理
本题所需前置知识
1 同余定理
如果 (a - b) % n 0 那么可以得到⼀个结论 a % n b % n 。即如果两个数相减的差能被n整除那么这两个数对n取模的结果相同
如 (26 - 2) % 12 0 那么 26 % 12 2 % 12 2
2 c 中负数取模结果的修正
c 中关于负数的取模运算结果是「把负数当成正数取模之后的结果加上⼀个负号」
如 -1 % 3 -(1 % 3) -1
由于余数在接下来的代码中会充当下标所以余数不能为负数故而有修正余数的情况
(a % n n) % n
若是a%n的结果为负数那么n就会是正数当然若是a%n的结果本身就是正数那么n就改变了故而%n
当a%n的结果为负数修正后依然比n小故而%n不会发生改变
当a%n的结果为正数无需修正但n使得结果变了又%n让变了的结果变回原样 枚举所有子数组可以每次固定一个起始位置向后枚举我们当然也可以每次固定一个结尾位置向前枚举
i是任意位置那么以 i 为结尾的和可被k 整除的子数组个数就可以这么求
由图示我们知道要求[0,i]区间内绿线的个数只要知道红线的个数即前缀和为x的个数就可以了又sum%kx%k
那么我们只需要知道在[0,i-1]内前缀和即x%ksum%k的个数即可
hash表统计前缀和%k的余数出现的次数
细节问题hash[0] 1 ,当i位置的前缀和本身sum就是能被k整除的[0,i]区间本身就是一个合法子数组那么x0
代码实现
class Solution
{
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,int hash;hash[0] 1;//0这个数(这个前缀和的余数也可以写成hash[0%k]1int ret 0;int sum 0;for(auto e:nums){sume;//当前位置的前缀和int r (sum%kk)%k;//修正后的余数if(hash.count(r)){rethash[r];}hash[r];}return ret;}
};
