主机网站建设制作,天津西青区天气预报,淘宝客网站的建设,中国国家培训网一、题目
给定一个整数数组 nums 和一个整数 k #xff0c;返回其中元素之和可被 k 整除的#xff08;连续、非空#xff09; 子数组 的数目。
子数组 是数组的 连续 部分。 示例 1#xff1a;
输入#xff1a;nums [4,5,0,-2,-3,1], k 5
输出#xff1a;7
解释返回其中元素之和可被 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
二、思路解析
这也是一道求和的题这一类大部分都可以用前缀和进行优化。
另外这道题还涉及了一个小定理同余定理还有其修正具体请看下图 同余定理 如果 (a - b) % n 0 那么我们可以得到⼀个结论 a % n b % n 。⽤⽂字叙述就是如果两个数相减的差能被 n 整除那么这两个数对?n?取模的结果相同。
例如 (26 - 2) % 12 0 那么 26 % 12 2 % 12 2.
而关于负数 % 正数的结果修正这是因为它的结果恒为负数修正则是为了让他的结果变成正数。
例如 -1 % 3 (-1 % 3 3) % 3 2.
所以在这道题我们还得创建一个哈希表用于记录在 i 位置之前保存到哈希表 [ 0 , i - 1 ] 位置的余数 [ 即 (sum % k k ) % k ] 的值。
同余定理在这道题的运用其实就是在帮助我们完成如下等量代换 于是问题就变成 找到在 [0, i - 1] 区间内有多少前缀和的余数等于 sum[ i ] % k 的。 三、完整代码
class Solution {public int subarraysDivByK(int[] nums, int k) {MapInteger,Integer hash new HashMapInteger,Integer();hash.put(0 % k , 1);int ret 0;int n nums.length;int sum 0;for(int x : nums){sum x;int r (sum % k k) % k;ret hash.getOrDefault(r , 0);hash.put(r , hash.getOrDefault(r , 0) 1);}return ret;}
} 以上就是本篇博客的全部内容啦如有不足之处还请各位指出期待能和各位一起进步
