DeepSeek LeetCode 3729. 统计有序数组中可被 K 整除的子数组数量 JavaScript实现

LeetCode 3729. 统计有序数组中可被 K 整除的子数组数量核心思路本题的关键在于去重两个子数组只要数值序列相同就视为同一个。由于数组有序重复的子数组只能由连续相同的元素构成。两步策略1. 统计全部含重复用前缀和 哈希表统计所有和能被 k 整除的子数组2. 减去重复计数对每段连续相同元素减去重复统计的子数组数量---解法一直接枚举易理解ACjavascript/*** param {number[]} nums* param {number} k* return {number}*/var numGoodSubarrays function(nums, k) {// Step 1: 统计所有子数组含重复let ans 0;let prefix 0;const map new Map();map.set(0, 1);for (let x of nums) {prefix ((prefix x) % k k) % k; // 处理负数const count map.get(prefix) || 0;ans count;map.set(prefix, count 1);}// Step 2: 减去重复统计let i 0;const n nums.length;while (i n) {let j i 1;while (j n nums[j] nums[i]) j;const m j - i; // 连续相同元素个数const val nums[i];// 枚举所有可能的子数组长度for (let len 1; len m; len) {// 如果该长度组成的子数组和能被 k 整除if ((len * val) % k 0) {// 该长度有 (m - len 1) 个子数组但在 step1 中统计了 m - len 1 次// 只需要保留 1 个所以要减去 m - lenans - (m - len);}}i j;}return ans;};---解法二数学优化推荐利用 step k / gcd(k, v) 跳跃枚举避免遍历所有长度javascript/*** param {number[]} nums* param {number} k* return {number}*/var numGoodSubarrays function(nums, k) {// 特判k1 时所有子数组都满足不同子数组数量 nif (k 1) return nums.length;// Step 1: 统计所有子数组含重复let ans 0;let prefix 0;const map new Map();map.set(0, 1);for (let x of nums) {prefix ((prefix x) % k k) % k;const count map.get(prefix) || 0;ans count;map.set(prefix, count 1);}// Step 2: 减去重复统计const n nums.length;let i 0;while (i n) {let j i 1;while (j n nums[j] nums[i]) j;const m j - i; // 连续相同元素个数const val nums[i];// 数学优化只需要枚举能被 k 整除的长度// 步长 step k / gcd(k, val)const step k / gcd(k, Math.abs(val));// 从 step 开始每次增加 step直到 mfor (let len step; len m; len step) {ans - (m - len);}i j;}return ans;};// 最大公约数辅助函数function gcd(a, b) {a Math.abs(a);b Math.abs(b);while (b ! 0) {[a, b] [b, a % b];}return a;}---详细示例javascript// 示例 1console.log(numGoodSubarrays([4,5,0,-2,-3,1], 5));// 输出7// 解释所有子数组和为 5 的倍数去重后有 7 个// 示例 2console.log(numGoodSubarrays([1,1,1,1], 2));// 输出4// 解释和为偶数的不同子数组[1,1], [1,1,1,1], 长度为2的段有2个但相同只算1个// 示例 3console.log(numGoodSubarrays([0,0,0,0], 3));// 输出4// 解释[0], [0,0], [0,0,0], [0,0,0,0] 共4个不同子数组---复杂度分析解法 时间复杂度 空间复杂度解法一 O(n Σm) 最坏 O(n²) O(n)解法二 O(n Σ(m/step)) 最坏 O(n²) O(n)---关键细节1. 前缀和取模((prefix x) % k k) % k 确保余数非负2. 去重逻辑· 对于长度为 m 的连续相同段长度为 len 的子数组有 (m - len 1) 个· 步骤1统计了全部我们只需要保留 1 个所以减去 (m - len)3. 数学优化· len * val % k 0 等价于 len 是 k / gcd(k, val) 的倍数· 只用枚举 len step, 2*step, 3*step, ...4. 边界情况· val 0 时gcd(k, 0) kstep 1所有长度都要去重· k 1 时直接返回 nums.length 即可---如果还想看其他语言的实现或有任何疑问欢迎继续提问