LeetCode 974 Subarray Sums Divisible by K All In One
LeetCode 974 能被 K 整除的子数组之和
erros
function subarraysDivByK(nums: number[], k: number): number {// -5 / 0 / 5 let count: number = 0;// 单个元素for(let i = 0; i < nums.length; i++) {if(Math.abs(nums[i] % k) === 0) {// console.log(`✅ nums[i] =`, nums[i])count += 1;}}// 多个元素let i = 0;let j = 0;let remainder = 0;for(i; i < nums.length - 1; i++) {remainder = nums[i];// console.log(`✅ sum =`, sum)// reminder 提醒 ❌// remainder 余数 ✅for(j = i + 1; j < nums.length; j++) {remainder = (remainder + nums[j]) % k;// console.log(`❌ sum =`, sum)if(Math.abs(remainder) === 0) {count += 1;}}}return count;
};/* Time Limit Exceeded
66 / 73 testcases passednums =
[0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0]k =
10000*/// function subarraysDivByK(nums: number[], k: number): number {
// // -5 / 0 / 5
// let count: number = 0;
// // 单个元素
// for(let i = 0; i < nums.length; i++) {
// if(Math.abs(nums[i] % k) === 0) {
// // console.log(`✅ nums[i] =`, nums[i])
// count += 1;
// }
// }
// // 多个元素
// let i = 0;
// let j = 0;
// let sum = 0;
// for(i; i < nums.length - 1; i++) {
// sum = nums[i];
// // console.log(`✅ sum =`, sum)
// for(j = i + 1; j < nums.length; j++) {
// sum += nums[j];
// // console.log(`❌ sum =`, sum)
// if(Math.abs(sum % k) === 0) {
// count += 1;
// }
// }
// }
// return count;
// };// function subarraysDivByK(nums: number[], k: number): number {
// // -5 / 0 / 5
// let i = 0;
// let j = 0;
// let sum = 0;
// let result = [];
// let temp = [];
// for(let i = 0; i < nums.length; i++) {
// if(Math.abs(nums[i] % k) === 0) {
// result.push([nums[i]]);
// }
// }
// for(i; i < nums.length - 1; i++) {
// // if(Math.abs(nums[i] % k) === 0) {
// // console.log(`✅ nums[i] =`, nums[i]);
// // result.push([nums[i]]);
// // console.log(`❓ result =`, result);
// // }
// temp = [];
// j = i + 1;
// temp.push(nums[i])
// for(j; j < nums.length; j++) {
// temp.push(nums[j])
// sum = temp.reduce((s, item) => s += item, 0);
// if(Math.abs(sum % k) === 0) {
// result.push(temp);
// // break;
// }
// console.log(`🚀 result =`, result, j);
// }
// // console.log(`🚀 result =`, result, j);
// }
// console.log(`❌ result =`, result);
// return result.length;
// };/* Output Limit Exceeded
38 / 73 testcases passednums =
[0,0,0,0,0,0,0,
....
,0,0,0,0,0,0,0]k =
1000*/
solutions
prefix sum / 前缀和
function subarraysDivByK(nums: number[], k: number): number {const map = new Map<number, number>();map.set(0, 1);let sum = 0;let count = 0;let remainder = 0;for (let num of nums) {sum += num;// ???remainder = ((sum % k) + k) % k;if (map.has(remainder)) {count += map.get(remainder)!;}map.set(remainder, (map.get(remainder) || 0) + 1);}return count;
};
demos
https://leetcode.com/problems/subarray-sums-divisible-by-k/description/?source=submission-ac
(🐞 反爬虫测试!打击盗版⚠️)如果你看到这个信息, 说明这是一篇剽窃的文章,请访问 https://www.cnblogs.com/xgqfrms/ 查看原创文章!
refs
https://www.youtube.com/watch?v=22ZTHGKDSS4
https://www.youtube.com/watch?v=6lik5HreRHI
https://www.youtube.com/watch?v=F71NLEXIUXM
©xgqfrms 2012-2021
www.cnblogs.com/xgqfrms 发布文章使用:只允许注册用户才可以访问!
原创文章,版权所有©️xgqfrms, 禁止转载 🈲️,侵权必究⚠️!