奥林匹克做校服的网站,移动互联网服务管理中心,wordpress 恢复备份,网络规划设计师招聘【问题描述】[中等]
给定一个整数数组 A#xff0c;返回其中元素之和可被 K 整除的#xff08;连续、非空#xff09;子数组的数目。示例#xff1a;输入#xff1a;A [4,5,0,-2,-3,1], K 5
输出#xff1a;7
解释#xff1a;
有 7 个子数组满足其元素之和可被 K 5 …【问题描述】[中等]
给定一个整数数组 A返回其中元素之和可被 K 整除的连续、非空子数组的数目。示例输入A [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]【解答思路】
1. 暴力不通过
时间复杂度O(N^2) 空间复杂度O(1) public int subarraysDivByK(int[] A, int K) {int n A.length;int res 0;for (int i 0; i n; i) {int sum 0;for (int j i; j n; j) {if ((sum A[j]) % K 0) {res;}}}return res;}2. 前缀和 同余思想
转化为同余的思想
时间复杂度O(N) 空间复杂度O(N)
数组维护 // 计算同余法// 用sum保存前n个数之和// 计算每个sum的余数保存// 余数相同则可以整除 如// A [4,5,0,-2,-3,1], K 5// p[0] 4, p[1] 9, p[2] 9, p[3] 7, p[4] 4, p[5] 5// 余数对应 4,4,4,2,4,0;// 余数4有4个排列组合法计算4*3/2 6// 0余数相当于整除用排列组合法(初始0赋值1) 2*1/2 1;// 最终答案为7public int subarraysDivByK(int[] A, int K) {int res 0;// 记录当前前缀和int preSum 0;// 因为K固定因此可以使用数组代替哈希表mod[i] j代表余数为i的前缀和出现了j次int[] mod new int[K];// 余数为0的状况也就是直接被整除的情况要提前放个1考虑比如 A {K}mod[0] 1;for (int value : A) {// 更新前缀和preSum value;// 计算modjava注意int m (preSum % K K) % K;// 更新结果res mod[m];// 更新余数集记录mod[m];}return res;}HashSet
class Solution {public int subarraysDivByK(int[] A, int K) {MapInteger, Integer record new HashMap();record.put(0, 1);int sum 0, ans 0;for (int elem: A) {sum elem;// 注意 Java 取模的特殊性当被除数为负数时取模结果为负数需要纠正int modulus (sum % K K) % K;int same record.getOrDefault(modulus, 0);ans same;record.put(modulus, same 1);}return ans;}
}
【总结】
1.取余问题
对于任何同号的两个整数其取余结果没有争议所有语言的运算原则都是使商尽可能小。对于异号的两个整数C/Java语言的原则是使商尽可能大很多新型语言和网页计算器的原则是使商尽可能小。
//被除数是负数
CG 编译 cout (-7) % 3; // 输出 -1Java1.6 System.out.println((-7) % 3); // 输出 -1Python 2.6 (-7) % 3 // 输出 2百度计算器(-7) mod 3 2Google 计算器(-7) mod 3 2
//除数是负数
CG 编译 cout 7 % (-3); // 输出 1Java1.6 System.out.println(7 % (-3)); // 输出 1Python 2.6 输出 -2百度计算器7 mod (-3) -2Google 计算器 7 mod (-3) -2】//被除数和除数同为负号
CG 编译 cout (-7) % (-3); // 输出 -1Java1.6 System.out.println((-7) % (-3)); // 输出 -1Python 2.6 输出 -1百度计算器-7 mod (-3) -1Google 计算器 -7 mod (-3) -1
2. 前缀和 涉及到数组求和
3.数学是个好东西
转载链接https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/guan-fang-ti-jie-tong-yu-fa-by-qi-xi-5/
参考链接https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/he-ke-bei-k-zheng-chu-de-zi-shu-zu-by-leetcode-sol/ 参考链接http://ceeji.net/blog/mod-in-real/
